/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include "igraph_topology.h"
#include "igraph_memory.h"
#include "igraph_adjlist.h"
#include "igraph_interface.h"
#include "igraph_interrupt_internal.h"
#include "igraph_constructors.h"
#include "igraph_conversion.h"
#include "igraph_stack.h"
#include "igraph_attributes.h"
#include "config.h"

const unsigned int igraph_i_isoclass_3[] = {  0, 1, 1, 3, 1, 5, 6, 7,
					      1, 6,10,11, 3, 7,11,15,
					      1, 6, 5, 7,10,21,21,23,
					      6,25,21,27,11,27,30,31,
					      1,10, 6,11, 6,21,25,27,
					      5,21,21,30, 7,23,27,31,
					      3,11, 7,15,11,30,27,31,
					      7,27,23,31,15,31,31,63 };

const unsigned int igraph_i_isoclass_3_idx[] = { 0, 4, 16, 1, 0, 32, 2, 8, 0 };

const unsigned int igraph_i_isoclass_4[] = { 
     0,   1,   1,   3,   1,   3,   3,   7,   1,   9,  10,  11,  10,
    11,  14,  15,   1,  10,  18,  19,  20,  21,  22,  23,   3,  11,
    19,  27,  21,  29,  30,  31,   1,  10,  20,  21,  18,  19,  22,
    23,   3,  11,  21,  29,  19,  27,  30,  31,   3,  14,  22,  30,
    22,  30,  54,  55,   7,  15,  23,  31,  23,  31,  55,  63,   1,
    10,   9,  11,  10,  14,  11,  15,  18,  73,  73,  75,  76,  77,
    77,  79,  10,  81,  73,  83,  84,  85,  86,  87,  19,  83,  90,
    91,  92,  93,  94,  95,  20,  84,  98,  99, 100, 101, 102, 103,
    22,  86, 106, 107, 108, 109, 110, 111,  21,  85, 106, 115, 116,
   117, 118, 119,  23,  87, 122, 123, 124, 125, 126, 127,   1,  18,
    10,  19,  20,  22,  21,  23,  10,  73,  81,  83,  84,  86,  85,
    87,   9,  73,  73,  90,  98, 106, 106, 122,  11,  75,  83,  91,
    99, 107, 115, 123,  10,  76,  84,  92, 100, 108, 116, 124,  14,
    77,  85,  93, 101, 109, 117, 125,  11,  77,  86,  94, 102, 110,
   118, 126,  15,  79,  87,  95, 103, 111, 119, 127,   3,  19,  11,
    27,  21,  30,  29,  31,  19,  90,  83,  91,  92,  94,  93,  95,
    11,  83,  75,  91,  99, 115, 107, 123,  27,  91,  91, 219, 220,
   221, 221, 223,  21,  92,  99, 220, 228, 229, 230, 231,  30,  94,
   115, 221, 229, 237, 238, 239,  29,  93, 107, 221, 230, 238, 246,
   247,  31,  95, 123, 223, 231, 239, 247, 255,   1,  20,  10,  21,
    18,  22,  19,  23,  20,  98,  84,  99, 100, 102, 101, 103,  10,
    84,  76,  92, 100, 116, 108, 124,  21,  99,  92, 220, 228, 230,
   229, 231,  18, 100, 100, 228, 292, 293, 293, 295,  22, 102, 116,
   230, 293, 301, 302, 303,  19, 101, 108, 229, 293, 302, 310, 311,
    23, 103, 124, 231, 295, 303, 311, 319,   3,  21,  11,  29,  19,
    30,  27,  31,  22, 106,  86, 107, 108, 110, 109, 111,  14,  85,
    77,  93, 101, 117, 109, 125,  30, 115,  94, 221, 229, 238, 237,
   239,  22, 116, 102, 230, 293, 302, 301, 303,  54, 118, 118, 246,
   310, 365, 365, 367,  30, 117, 110, 238, 302, 373, 365, 375,  55,
   119, 126, 247, 311, 375, 382, 383,   3,  22,  14,  30,  22,  54,
    30,  55,  21, 106,  85, 115, 116, 118, 117, 119,  11,  86,  77,
    94, 102, 118, 110, 126,  29, 107,  93, 221, 230, 246, 238, 247,
    19, 108, 101, 229, 293, 310, 302, 311,  30, 110, 117, 238, 302,
   365, 373, 375,  27, 109, 109, 237, 301, 365, 365, 382,  31, 111,
   125, 239, 303, 367, 375, 383,   7,  23,  15,  31,  23,  55,  31,
    63,  23, 122,  87, 123, 124, 126, 125, 127,  15,  87,  79,  95,
   103, 119, 111, 127,  31, 123,  95, 223, 231, 247, 239, 255,  23,
   124, 103, 231, 295, 311, 303, 319,  55, 126, 119, 247, 311, 382,
   375, 383,  31, 125, 111, 239, 303, 375, 367, 383,  63, 127, 127,
   255, 319, 383, 383, 511,   1,  10,  10,  14,   9,  11,  11,  15,
    18,  73,  76,  77,  73,  75,  77,  79,  20,  84, 100, 101,  98,
    99, 102, 103,  22,  86, 108, 109, 106, 107, 110, 111,  10,  81,
    84,  85,  73,  83,  86,  87,  19,  83,  92,  93,  90,  91,  94,
    95,  21,  85, 116, 117, 106, 115, 118, 119,  23,  87, 124, 125,
   122, 123, 126, 127,  18,  76,  73,  77,  73,  77,  75,  79, 292,
   585, 585, 587, 585, 587, 587, 591, 100, 593, 594, 595, 596, 597,
   598, 599, 293, 601, 602, 603, 604, 605, 606, 607, 100, 593, 596,
   597, 594, 595, 598, 599, 293, 601, 604, 605, 602, 603, 606, 607,
   228, 625, 626, 627, 626, 627, 630, 631, 295, 633, 634, 635, 634,
   635, 638, 639,  20, 100,  84, 101,  98, 102,  99, 103, 100, 594,
   593, 595, 596, 598, 597, 599,  98, 596, 596, 659, 660, 661, 661,
   663, 102, 598, 666, 667, 661, 669, 670, 671,  84, 593, 674, 675,
   596, 666, 678, 679, 101, 595, 675, 683, 659, 667, 686, 687,  99,
   597, 678, 686, 661, 670, 694, 695, 103, 599, 679, 687, 663, 671,
   695, 703,  22, 108,  86, 109, 106, 110, 107, 111, 293, 602, 601,
   603, 604, 606, 605, 607, 102, 666, 598, 667, 661, 670, 669, 671,
   301, 729, 729, 731, 732, 733, 733, 735, 116, 737, 678, 739, 626,
   741, 742, 743, 302, 745, 746, 747, 748, 749, 750, 751, 230, 753,
   742, 755, 756, 757, 758, 759, 303, 761, 762, 763, 764, 765, 766,
   767,  10,  84,  81,  85,  73,  86,  83,  87, 100, 596, 593, 597,
   594, 598, 595, 599,  84, 674, 593, 675, 596, 678, 666, 679, 116,
   678, 737, 739, 626, 742, 741, 743,  76, 593, 593, 625, 585, 601,
   601, 633, 108, 666, 737, 753, 602, 729, 745, 761,  92, 675, 737,
   819, 604, 746, 822, 823, 124, 679, 826, 827, 634, 762, 830, 831,
    19,  92,  83,  93,  90,  94,  91,  95, 293, 604, 601, 605, 602,
   606, 603, 607, 101, 675, 595, 683, 659, 686, 667, 687, 302, 746,
   745, 747, 748, 750, 749, 751, 108, 737, 666, 753, 602, 745, 729,
   761, 310, 822, 822, 875, 876, 877, 877, 879, 229, 819, 741, 883,
   748, 885, 886, 887, 311, 823, 830, 891, 892, 893, 894, 895,  21,
   116,  85, 117, 106, 118, 115, 119, 228, 626, 625, 627, 626, 630,
   627, 631,  99, 678, 597, 686, 661, 694, 670, 695, 230, 742, 753,
   755, 756, 758, 757, 759,  92, 737, 675, 819, 604, 822, 746, 823,
   229, 741, 819, 883, 748, 886, 885, 887, 220, 739, 739, 947, 732,
   949, 949, 951, 231, 743, 827, 955, 764, 957, 958, 959,  23, 124,
    87, 125, 122, 126, 123, 127, 295, 634, 633, 635, 634, 638, 635,
   639, 103, 679, 599, 687, 663, 695, 671, 703, 303, 762, 761, 763,
   764, 766, 765, 767, 124, 826, 679, 827, 634, 830, 762, 831, 311,
   830, 823, 891, 892, 894, 893, 895, 231, 827, 743, 955, 764, 958,
   957, 959, 319, 831, 831,1019,1020,1021,1021,1023,   1,  18,  20,
    22,  10,  19,  21,  23,  10,  73,  84,  86,  81,  83,  85,  87,
    10,  76, 100, 108,  84,  92, 116, 124,  14,  77, 101, 109,  85,
    93, 117, 125,   9,  73,  98, 106,  73,  90, 106, 122,  11,  75,
    99, 107,  83,  91, 115, 123,  11,  77, 102, 110,  86,  94, 118,
   126,  15,  79, 103, 111,  87,  95, 119, 127,  20, 100,  98, 102,
    84, 101,  99, 103, 100, 594, 596, 598, 593, 595, 597, 599,  84,
   593, 596, 666, 674, 675, 678, 679, 101, 595, 659, 667, 675, 683,
   686, 687,  98, 596, 660, 661, 596, 659, 661, 663, 102, 598, 661,
   669, 666, 667, 670, 671,  99, 597, 661, 670, 678, 686, 694, 695,
   103, 599, 663, 671, 679, 687, 695, 703,  18, 292, 100, 293, 100,
   293, 228, 295,  76, 585, 593, 601, 593, 601, 625, 633,  73, 585,
   594, 602, 596, 604, 626, 634,  77, 587, 595, 603, 597, 605, 627,
   635,  73, 585, 596, 604, 594, 602, 626, 634,  77, 587, 597, 605,
   595, 603, 627, 635,  75, 587, 598, 606, 598, 606, 630, 638,  79,
   591, 599, 607, 599, 607, 631, 639,  22, 293, 102, 301, 116, 302,
   230, 303, 108, 602, 666, 729, 737, 745, 753, 761,  86, 601, 598,
   729, 678, 746, 742, 762, 109, 603, 667, 731, 739, 747, 755, 763,
   106, 604, 661, 732, 626, 748, 756, 764, 110, 606, 670, 733, 741,
   749, 757, 765, 107, 605, 669, 733, 742, 750, 758, 766, 111, 607,
   671, 735, 743, 751, 759, 767,  10, 100,  84, 116,  76, 108,  92,
   124,  84, 596, 674, 678, 593, 666, 675, 679,  81, 593, 593, 737,
   593, 737, 737, 826,  85, 597, 675, 739, 625, 753, 819, 827,  73,
   594, 596, 626, 585, 602, 604, 634,  86, 598, 678, 742, 601, 729,
   746, 762,  83, 595, 666, 741, 601, 745, 822, 830,  87, 599, 679,
   743, 633, 761, 823, 831,  21, 228,  99, 230,  92, 229, 220, 231,
   116, 626, 678, 742, 737, 741, 739, 743,  85, 625, 597, 753, 675,
   819, 739, 827, 117, 627, 686, 755, 819, 883, 947, 955, 106, 626,
   661, 756, 604, 748, 732, 764, 118, 630, 694, 758, 822, 886, 949,
   957, 115, 627, 670, 757, 746, 885, 949, 958, 119, 631, 695, 759,
   823, 887, 951, 959,  19, 293, 101, 302, 108, 310, 229, 311,  92,
   604, 675, 746, 737, 822, 819, 823,  83, 601, 595, 745, 666, 822,
   741, 830,  93, 605, 683, 747, 753, 875, 883, 891,  90, 602, 659,
   748, 602, 876, 748, 892,  94, 606, 686, 750, 745, 877, 885, 893,
    91, 603, 667, 749, 729, 877, 886, 894,  95, 607, 687, 751, 761,
   879, 887, 895,  23, 295, 103, 303, 124, 311, 231, 319, 124, 634,
   679, 762, 826, 830, 827, 831,  87, 633, 599, 761, 679, 823, 743,
   831, 125, 635, 687, 763, 827, 891, 955,1019, 122, 634, 663, 764,
   634, 892, 764,1020, 126, 638, 695, 766, 830, 894, 958,1021, 123,
   635, 671, 765, 762, 893, 957,1021, 127, 639, 703, 767, 831, 895,
   959,1023,   3,  19,  21,  30,  11,  27,  29,  31,  19,  90,  92,
    94,  83,  91,  93,  95,  21,  92, 228, 229,  99, 220, 230, 231,
    30,  94, 229, 237, 115, 221, 238, 239,  11,  83,  99, 115,  75,
    91, 107, 123,  27,  91, 220, 221,  91, 219, 221, 223,  29,  93,
   230, 238, 107, 221, 246, 247,  31,  95, 231, 239, 123, 223, 247,
   255,  22, 108, 106, 110,  86, 109, 107, 111, 293, 602, 604, 606,
   601, 603, 605, 607, 116, 737, 626, 741, 678, 739, 742, 743, 302,
   745, 748, 749, 746, 747, 750, 751, 102, 666, 661, 670, 598, 667,
   669, 671, 301, 729, 732, 733, 729, 731, 733, 735, 230, 753, 756,
   757, 742, 755, 758, 759, 303, 761, 764, 765, 762, 763, 766, 767,
    22, 293, 116, 302, 102, 301, 230, 303, 108, 602, 737, 745, 666,
   729, 753, 761, 106, 604, 626, 748, 661, 732, 756, 764, 110, 606,
   741, 749, 670, 733, 757, 765,  86, 601, 678, 746, 598, 729, 742,
   762, 109, 603, 739, 747, 667, 731, 755, 763, 107, 605, 742, 750,
   669, 733, 758, 766, 111, 607, 743, 751, 671, 735, 759, 767,  54,
   310, 118, 365, 118, 365, 246, 367, 310, 876, 822, 877, 822, 877,
   875, 879, 118, 822, 630, 886, 694, 949, 758, 957, 365, 877, 886,
  1755, 949,1757,1758,1759, 118, 822, 694, 949, 630, 886, 758, 957,
   365, 877, 949,1757, 886,1755,1758,1759, 246, 875, 758,1758, 758,
  1758,1782,1783, 367, 879, 957,1759, 957,1759,1783,1791,  14, 101,
    85, 117,  77, 109,  93, 125, 101, 659, 675, 686, 595, 667, 683,
   687,  85, 675, 625, 819, 597, 739, 753, 827, 117, 686, 819, 947,
   627, 755, 883, 955,  77, 595, 597, 627, 587, 603, 605, 635, 109,
   667, 739, 755, 603, 731, 747, 763,  93, 683, 753, 883, 605, 747,
   875, 891, 125, 687, 827, 955, 635, 763, 891,1019,  30, 229, 115,
   238,  94, 237, 221, 239, 302, 748, 746, 750, 745, 749, 747, 751,
   117, 819, 627, 883, 686, 947, 755, 955, 373, 885, 885,1883, 885,
  1883,1883,1887, 110, 741, 670, 757, 606, 749, 733, 765, 365, 886,
   949,1758, 877,1755,1757,1759, 238, 883, 757,1907, 750,1883,1758,
  1911, 375, 887, 958,1911, 893,1917,1918,1919,  30, 302, 117, 373,
   110, 365, 238, 375, 229, 748, 819, 885, 741, 886, 883, 887, 115,
   746, 627, 885, 670, 949, 757, 958, 238, 750, 883,1883, 757,1758,
  1907,1911,  94, 745, 686, 885, 606, 877, 750, 893, 237, 749, 947,
  1883, 749,1755,1883,1917, 221, 747, 755,1883, 733,1757,1758,1918,
   239, 751, 955,1887, 765,1759,1911,1919,  55, 311, 119, 375, 126,
   382, 247, 383, 311, 892, 823, 893, 830, 894, 891, 895, 119, 823,
   631, 887, 695, 951, 759, 959, 375, 893, 887,1917, 958,1918,1911,
  1919, 126, 830, 695, 958, 638, 894, 766,1021, 382, 894, 951,1918,
   894,2029,1918,2031, 247, 891, 759,1911, 766,1918,1783,2039, 383,
   895, 959,1919,1021,2031,2039,2047,   1,  20,  18,  22,  10,  21,
    19,  23,  20,  98, 100, 102,  84,  99, 101, 103,  18, 100, 292,
   293, 100, 228, 293, 295,  22, 102, 293, 301, 116, 230, 302, 303,
    10,  84, 100, 116,  76,  92, 108, 124,  21,  99, 228, 230,  92,
   220, 229, 231,  19, 101, 293, 302, 108, 229, 310, 311,  23, 103,
   295, 303, 124, 231, 311, 319,  10,  84,  73,  86,  81,  85,  83,
    87, 100, 596, 594, 598, 593, 597, 595, 599,  76, 593, 585, 601,
   593, 625, 601, 633, 108, 666, 602, 729, 737, 753, 745, 761,  84,
   674, 596, 678, 593, 675, 666, 679, 116, 678, 626, 742, 737, 739,
   741, 743,  92, 675, 604, 746, 737, 819, 822, 823, 124, 679, 634,
   762, 826, 827, 830, 831,  10, 100,  76, 108,  84, 116,  92, 124,
    84, 596, 593, 666, 674, 678, 675, 679,  73, 594, 585, 602, 596,
   626, 604, 634,  86, 598, 601, 729, 678, 742, 746, 762,  81, 593,
   593, 737, 593, 737, 737, 826,  85, 597, 625, 753, 675, 739, 819,
   827,  83, 595, 601, 745, 666, 741, 822, 830,  87, 599, 633, 761,
   679, 743, 823, 831,  14, 101,  77, 109,  85, 117,  93, 125, 101,
   659, 595, 667, 675, 686, 683, 687,  77, 595, 587, 603, 597, 627,
   605, 635, 109, 667, 603, 731, 739, 755, 747, 763,  85, 675, 597,
   739, 625, 819, 753, 827, 117, 686, 627, 755, 819, 947, 883, 955,
    93, 683, 605, 747, 753, 883, 875, 891, 125, 687, 635, 763, 827,
   955, 891,1019,   9,  98,  73, 106,  73, 106,  90, 122,  98, 660,
   596, 661, 596, 661, 659, 663,  73, 596, 585, 604, 594, 626, 602,
   634, 106, 661, 604, 732, 626, 756, 748, 764,  73, 596, 594, 626,
   585, 604, 602, 634, 106, 661, 626, 756, 604, 732, 748, 764,  90,
   659, 602, 748, 602, 748, 876, 892, 122, 663, 634, 764, 634, 764,
   892,1020,  11,  99,  75, 107,  83, 115,  91, 123, 102, 661, 598,
   669, 666, 670, 667, 671,  77, 597, 587, 605, 595, 627, 603, 635,
   110, 670, 606, 733, 741, 757, 749, 765,  86, 678, 598, 742, 601,
   746, 729, 762, 118, 694, 630, 758, 822, 949, 886, 957,  94, 686,
   606, 750, 745, 885, 877, 893, 126, 695, 638, 766, 830, 958, 894,
  1021,  11, 102,  77, 110,  86, 118,  94, 126,  99, 661, 597, 670,
   678, 694, 686, 695,  75, 598, 587, 606, 598, 630, 606, 638, 107,
   669, 605, 733, 742, 758, 750, 766,  83, 666, 595, 741, 601, 822,
   745, 830, 115, 670, 627, 757, 746, 949, 885, 958,  91, 667, 603,
   749, 729, 886, 877, 894, 123, 671, 635, 765, 762, 957, 893,1021,
    15, 103,  79, 111,  87, 119,  95, 127, 103, 663, 599, 671, 679,
   695, 687, 703,  79, 599, 591, 607, 599, 631, 607, 639, 111, 671,
   607, 735, 743, 759, 751, 767,  87, 679, 599, 743, 633, 823, 761,
   831, 119, 695, 631, 759, 823, 951, 887, 959,  95, 687, 607, 751,
   761, 887, 879, 895, 127, 703, 639, 767, 831, 959, 895,1023,   3,
    21,  19,  30,  11,  29,  27,  31,  22, 106, 108, 110,  86, 107,
   109, 111,  22, 116, 293, 302, 102, 230, 301, 303,  54, 118, 310,
   365, 118, 246, 365, 367,  14,  85, 101, 117,  77,  93, 109, 125,
    30, 115, 229, 238,  94, 221, 237, 239,  30, 117, 302, 373, 110,
   238, 365, 375,  55, 119, 311, 375, 126, 247, 382, 383,  19,  92,
    90,  94,  83,  93,  91,  95, 293, 604, 602, 606, 601, 605, 603,
   607, 108, 737, 602, 745, 666, 753, 729, 761, 310, 822, 876, 877,
   822, 875, 877, 879, 101, 675, 659, 686, 595, 683, 667, 687, 302,
   746, 748, 750, 745, 747, 749, 751, 229, 819, 748, 885, 741, 883,
   886, 887, 311, 823, 892, 893, 830, 891, 894, 895,  21, 228,  92,
   229,  99, 230, 220, 231, 116, 626, 737, 741, 678, 742, 739, 743,
   106, 626, 604, 748, 661, 756, 732, 764, 118, 630, 822, 886, 694,
   758, 949, 957,  85, 625, 675, 819, 597, 753, 739, 827, 117, 627,
   819, 883, 686, 755, 947, 955, 115, 627, 746, 885, 670, 757, 949,
   958, 119, 631, 823, 887, 695, 759, 951, 959,  30, 229,  94, 237,
   115, 238, 221, 239, 302, 748, 745, 749, 746, 750, 747, 751, 110,
   741, 606, 749, 670, 757, 733, 765, 365, 886, 877,1755, 949,1758,
  1757,1759, 117, 819, 686, 947, 627, 883, 755, 955, 373, 885, 885,
  1883, 885,1883,1883,1887, 238, 883, 750,1883, 757,1907,1758,1911,
   375, 887, 893,1917, 958,1911,1918,1919,  11,  99,  83, 115,  75,
   107,  91, 123, 102, 661, 666, 670, 598, 669, 667, 671,  86, 678,
   601, 746, 598, 742, 729, 762, 118, 694, 822, 949, 630, 758, 886,
   957,  77, 597, 595, 627, 587, 605, 603, 635, 110, 670, 741, 757,
   606, 733, 749, 765,  94, 686, 745, 885, 606, 750, 877, 893, 126,
   695, 830, 958, 638, 766, 894,1021,  27, 220,  91, 221,  91, 221,
   219, 223, 301, 732, 729, 733, 729, 733, 731, 735, 109, 739, 603,
   747, 667, 755, 731, 763, 365, 949, 877,1757, 886,1758,1755,1759,
   109, 739, 667, 755, 603, 747, 731, 763, 365, 949, 886,1758, 877,
  1757,1755,1759, 237, 947, 749,1883, 749,1883,1755,1917, 382, 951,
   894,1918, 894,1918,2029,2031,  29, 230,  93, 238, 107, 246, 221,
   247, 230, 756, 753, 757, 742, 758, 755, 759, 107, 742, 605, 750,
   669, 758, 733, 766, 246, 758, 875,1758, 758,1782,1758,1783,  93,
   753, 683, 883, 605, 875, 747, 891, 238, 757, 883,1907, 750,1758,
  1883,1911, 221, 755, 747,1883, 733,1758,1757,1918, 247, 759, 891,
  1911, 766,1783,1918,2039,  31, 231,  95, 239, 123, 247, 223, 255,
   303, 764, 761, 765, 762, 766, 763, 767, 111, 743, 607, 751, 671,
   759, 735, 767, 367, 957, 879,1759, 957,1783,1759,1791, 125, 827,
   687, 955, 635, 891, 763,1019, 375, 958, 887,1911, 893,1918,1917,
  1919, 239, 955, 751,1887, 765,1911,1759,1919, 383, 959, 895,1919,
  1021,2039,2031,2047,   3,  22,  22,  54,  14,  30,  30,  55,  21,
   106, 116, 118,  85, 115, 117, 119,  19, 108, 293, 310, 101, 229,
   302, 311,  30, 110, 302, 365, 117, 238, 373, 375,  11,  86, 102,
   118,  77,  94, 110, 126,  29, 107, 230, 246,  93, 221, 238, 247,
    27, 109, 301, 365, 109, 237, 365, 382,  31, 111, 303, 367, 125,
   239, 375, 383,  21, 116, 106, 118,  85, 117, 115, 119, 228, 626,
   626, 630, 625, 627, 627, 631,  92, 737, 604, 822, 675, 819, 746,
   823, 229, 741, 748, 886, 819, 883, 885, 887,  99, 678, 661, 694,
   597, 686, 670, 695, 230, 742, 756, 758, 753, 755, 757, 759, 220,
   739, 732, 949, 739, 947, 949, 951, 231, 743, 764, 957, 827, 955,
   958, 959,  19, 293, 108, 310, 101, 302, 229, 311,  92, 604, 737,
   822, 675, 746, 819, 823,  90, 602, 602, 876, 659, 748, 748, 892,
    94, 606, 745, 877, 686, 750, 885, 893,  83, 601, 666, 822, 595,
   745, 741, 830,  93, 605, 753, 875, 683, 747, 883, 891,  91, 603,
   729, 877, 667, 749, 886, 894,  95, 607, 761, 879, 687, 751, 887,
   895,  30, 302, 110, 365, 117, 373, 238, 375, 229, 748, 741, 886,
   819, 885, 883, 887,  94, 745, 606, 877, 686, 885, 750, 893, 237,
   749, 749,1755, 947,1883,1883,1917, 115, 746, 670, 949, 627, 885,
   757, 958, 238, 750, 757,1758, 883,1883,1907,1911, 221, 747, 733,
  1757, 755,1883,1758,1918, 239, 751, 765,1759, 955,1887,1911,1919,
    11, 102,  86, 118,  77, 110,  94, 126,  99, 661, 678, 694, 597,
   670, 686, 695,  83, 666, 601, 822, 595, 741, 745, 830, 115, 670,
   746, 949, 627, 757, 885, 958,  75, 598, 598, 630, 587, 606, 606,
   638, 107, 669, 742, 758, 605, 733, 750, 766,  91, 667, 729, 886,
   603, 749, 877, 894, 123, 671, 762, 957, 635, 765, 893,1021,  29,
   230, 107, 246,  93, 238, 221, 247, 230, 756, 742, 758, 753, 757,
   755, 759,  93, 753, 605, 875, 683, 883, 747, 891, 238, 757, 750,
  1758, 883,1907,1883,1911, 107, 742, 669, 758, 605, 750, 733, 766,
   246, 758, 758,1782, 875,1758,1758,1783, 221, 755, 733,1758, 747,
  1883,1757,1918, 247, 759, 766,1783, 891,1911,1918,2039,  27, 301,
   109, 365, 109, 365, 237, 382, 220, 732, 739, 949, 739, 949, 947,
   951,  91, 729, 603, 877, 667, 886, 749, 894, 221, 733, 747,1757,
   755,1758,1883,1918,  91, 729, 667, 886, 603, 877, 749, 894, 221,
   733, 755,1758, 747,1757,1883,1918, 219, 731, 731,1755, 731,1755,
  1755,2029, 223, 735, 763,1759, 763,1759,1917,2031,  31, 303, 111,
   367, 125, 375, 239, 383, 231, 764, 743, 957, 827, 958, 955, 959,
    95, 761, 607, 879, 687, 887, 751, 895, 239, 765, 751,1759, 955,
  1911,1887,1919, 123, 762, 671, 957, 635, 893, 765,1021, 247, 766,
   759,1783, 891,1918,1911,2039, 223, 763, 735,1759, 763,1917,1759,
  2031, 255, 767, 767,1791,1019,1919,1919,2047,   7,  23,  23,  55,
    15,  31,  31,  63,  23, 122, 124, 126,  87, 123, 125, 127,  23,
   124, 295, 311, 103, 231, 303, 319,  55, 126, 311, 382, 119, 247,
   375, 383,  15,  87, 103, 119,  79,  95, 111, 127,  31, 123, 231,
   247,  95, 223, 239, 255,  31, 125, 303, 375, 111, 239, 367, 383,
    63, 127, 319, 383, 127, 255, 383, 511,  23, 124, 122, 126,  87,
   125, 123, 127, 295, 634, 634, 638, 633, 635, 635, 639, 124, 826,
   634, 830, 679, 827, 762, 831, 311, 830, 892, 894, 823, 891, 893,
   895, 103, 679, 663, 695, 599, 687, 671, 703, 303, 762, 764, 766,
   761, 763, 765, 767, 231, 827, 764, 958, 743, 955, 957, 959, 319,
   831,1020,1021, 831,1019,1021,1023,  23, 295, 124, 311, 103, 303,
   231, 319, 124, 634, 826, 830, 679, 762, 827, 831, 122, 634, 634,
   892, 663, 764, 764,1020, 126, 638, 830, 894, 695, 766, 958,1021,
    87, 633, 679, 823, 599, 761, 743, 831, 125, 635, 827, 891, 687,
   763, 955,1019, 123, 635, 762, 893, 671, 765, 957,1021, 127, 639,
   831, 895, 703, 767, 959,1023,  55, 311, 126, 382, 119, 375, 247,
   383, 311, 892, 830, 894, 823, 893, 891, 895, 126, 830, 638, 894,
   695, 958, 766,1021, 382, 894, 894,2029, 951,1918,1918,2031, 119,
   823, 695, 951, 631, 887, 759, 959, 375, 893, 958,1918, 887,1917,
  1911,1919, 247, 891, 766,1918, 759,1911,1783,2039, 383, 895,1021,
  2031, 959,1919,2039,2047,  15, 103,  87, 119,  79, 111,  95, 127,
   103, 663, 679, 695, 599, 671, 687, 703,  87, 679, 633, 823, 599,
   743, 761, 831, 119, 695, 823, 951, 631, 759, 887, 959,  79, 599,
   599, 631, 591, 607, 607, 639, 111, 671, 743, 759, 607, 735, 751,
   767,  95, 687, 761, 887, 607, 751, 879, 895, 127, 703, 831, 959,
   639, 767, 895,1023,  31, 231, 123, 247,  95, 239, 223, 255, 303,
   764, 762, 766, 761, 765, 763, 767, 125, 827, 635, 891, 687, 955,
   763,1019, 375, 958, 893,1918, 887,1911,1917,1919, 111, 743, 671,
   759, 607, 751, 735, 767, 367, 957, 957,1783, 879,1759,1759,1791,
   239, 955, 765,1911, 751,1887,1759,1919, 383, 959,1021,2039, 895,
  1919,2031,2047,  31, 303, 125, 375, 111, 367, 239, 383, 231, 764,
   827, 958, 743, 957, 955, 959, 123, 762, 635, 893, 671, 957, 765,
  1021, 247, 766, 891,1918, 759,1783,1911,2039,  95, 761, 687, 887,
   607, 879, 751, 895, 239, 765, 955,1911, 751,1759,1887,1919, 223,
   763, 763,1917, 735,1759,1759,2031, 255, 767,1019,1919, 767,1791,
  1919,2047,  63, 319, 127, 383, 127, 383, 255, 511, 319,1020, 831,
  1021, 831,1021,1019,1023, 127, 831, 639, 895, 703, 959, 767,1023,
   383,1021, 895,2031, 959,2039,1919,2047, 127, 831, 703, 959, 639,
   895, 767,1023, 383,1021, 959,2039, 895,2031,1919,2047, 255,1019,
   767,1919, 767,1919,1791,2047, 511,1023,1023,2047,1023,2047,2047,
  4095 };

const unsigned int igraph_i_isoclass_4_idx[] = {
  0, 8, 64, 512, 1, 0, 128, 1024, 2, 16, 0, 2048, 4, 32, 256, 0 };

const unsigned int igraph_i_isoclass_3u[] = { 0,1,1,3,1,3,3,7 };

const unsigned int igraph_i_isoclass_3u_idx[] = { 0,1,2,1,0,4,2,4,0 };

const unsigned int igraph_i_isoclass_4u[] = {
  0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3,11,12,13,13,15, 1, 3,12,13, 3,11,13,15, 3, 7,
 13,15,13,15,30,31, 1,12, 3,13, 3,13,11,15, 3,13, 7,15,13,30,15,31, 3,13,13,30,
  7,15,15,31,11,15,15,31,15,31,31,63 };

const unsigned int igraph_i_isoclass_4u_idx[] = {
  0, 1, 2, 8, 1, 0, 4, 16, 2, 4, 0, 32, 8, 16, 32, 0 };

const unsigned int igraph_i_isoclass2_3[] = {
 0, 1, 1, 2, 1, 3, 4, 5, 1, 4, 6, 7, 2, 5, 7, 8, 1, 4, 3, 5, 6, 9, 9,10, 4,11,
 9,12, 7,12,13,14, 1, 6, 4, 7, 4, 9,11,12, 3, 9, 9,13, 5,10,12,14, 2, 7, 5, 8,
 7,13,12,14, 5,12,10,14, 8,14,14,15
};

const unsigned int igraph_i_isoclass2_3u[] = {
  0,1,1,2,1,2,2,3 
};

const unsigned int igraph_i_isoclass2_4u[] = { 
 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 4, 5, 6, 6, 7, 1, 2, 5, 6, 2, 4, 6, 7, 2, 3,
 6, 7, 6, 7, 8, 9, 1, 5, 2, 6, 2, 6, 4, 7, 2, 6, 3, 7, 6, 8, 7, 9, 2, 6, 6, 8,
 3, 7, 7, 9, 4, 7, 7, 9, 7, 9, 9,10
};

const unsigned int igraph_i_isoclass2_4[] = {
  0,  1,  1,  2,  1,  2,  2,  3,  1,  4,  5,  6,  5,  6,  7,  8,  1,  5,  9, 10,
 11, 12, 13, 14,  2,  6, 10, 15, 12, 16, 17, 18,  1,  5, 11, 12,  9, 10, 13, 14,
  2,  6, 12, 16, 10, 15, 17, 18,  2,  7, 13, 17, 13, 17, 19, 20,  3,  8, 14, 18,
 14, 18, 20, 21,  1,  5,  4,  6,  5,  7,  6,  8,  9, 22, 22, 23, 24, 25, 25, 26,
  5, 27, 22, 28, 29, 30, 31, 32, 10, 28, 33, 34, 35, 36, 37, 38, 11, 29, 39, 40,
 41, 42, 43, 44, 13, 31, 45, 46, 47, 48, 49, 50, 12, 30, 45, 51, 52, 53, 54, 55,
 14, 32, 56, 57, 58, 59, 60, 61,  1,  9,  5, 10, 11, 13, 12, 14,  5, 22, 27, 28,
 29, 31, 30, 32,  4, 22, 22, 33, 39, 45, 45, 56,  6, 23, 28, 34, 40, 46, 51, 57,
  5, 24, 29, 35, 41, 47, 52, 58,  7, 25, 30, 36, 42, 48, 53, 59,  6, 25, 31, 37,
 43, 49, 54, 60,  8, 26, 32, 38, 44, 50, 55, 61,  2, 10,  6, 15, 12, 17, 16, 18,
 10, 33, 28, 34, 35, 37, 36, 38,  6, 28, 23, 34, 40, 51, 46, 57, 15, 34, 34, 62,
 63, 64, 64, 65, 12, 35, 40, 63, 66, 67, 68, 69, 17, 37, 51, 64, 67, 70, 71, 72,
 16, 36, 46, 64, 68, 71, 73, 74, 18, 38, 57, 65, 69, 72, 74, 75,  1, 11,  5, 12,
  9, 13, 10, 14, 11, 39, 29, 40, 41, 43, 42, 44,  5, 29, 24, 35, 41, 52, 47, 58,
 12, 40, 35, 63, 66, 68, 67, 69,  9, 41, 41, 66, 76, 77, 77, 78, 13, 43, 52, 68,
 77, 79, 80, 81, 10, 42, 47, 67, 77, 80, 82, 83, 14, 44, 58, 69, 78, 81, 83, 84,
  2, 12,  6, 16, 10, 17, 15, 18, 13, 45, 31, 46, 47, 49, 48, 50,  7, 30, 25, 36,
 42, 53, 48, 59, 17, 51, 37, 64, 67, 71, 70, 72, 13, 52, 43, 68, 77, 80, 79, 81,
 19, 54, 54, 73, 82, 85, 85, 86, 17, 53, 49, 71, 80, 87, 85, 88, 20, 55, 60, 74,
 83, 88, 89, 90,  2, 13,  7, 17, 13, 19, 17, 20, 12, 45, 30, 51, 52, 54, 53, 55,
  6, 31, 25, 37, 43, 54, 49, 60, 16, 46, 36, 64, 68, 73, 71, 74, 10, 47, 42, 67,
 77, 82, 80, 83, 17, 49, 53, 71, 80, 85, 87, 88, 15, 48, 48, 70, 79, 85, 85, 89,
 18, 50, 59, 72, 81, 86, 88, 90,  3, 14,  8, 18, 14, 20, 18, 21, 14, 56, 32, 57,
 58, 60, 59, 61,  8, 32, 26, 38, 44, 55, 50, 61, 18, 57, 38, 65, 69, 74, 72, 75,
 14, 58, 44, 69, 78, 83, 81, 84, 20, 60, 55, 74, 83, 89, 88, 90, 18, 59, 50, 72,
 81, 88, 86, 90, 21, 61, 61, 75, 84, 90, 90, 91,  1,  5,  5,  7,  4,  6,  6,  8,
  9, 22, 24, 25, 22, 23, 25, 26, 11, 29, 41, 42, 39, 40, 43, 44, 13, 31, 47, 48,
 45, 46, 49, 50,  5, 27, 29, 30, 22, 28, 31, 32, 10, 28, 35, 36, 33, 34, 37, 38,
 12, 30, 52, 53, 45, 51, 54, 55, 14, 32, 58, 59, 56, 57, 60, 61,  9, 24, 22, 25,
 22, 25, 23, 26, 76, 92, 92, 93, 92, 93, 93, 94, 41, 95, 96, 97, 98, 99,100,101,
 77,102,103,104,105,106,107,108, 41, 95, 98, 99, 96, 97,100,101, 77,102,105,106,
103,104,107,108, 66,109,110,111,110,111,112,113, 78,114,115,116,115,116,117,118,
 11, 41, 29, 42, 39, 43, 40, 44, 41, 96, 95, 97, 98,100, 99,101, 39, 98, 98,119,
120,121,121,122, 43,100,123,124,121,125,126,127, 29, 95,128,129, 98,123,130,131,
 42, 97,129,132,119,124,133,134, 40, 99,130,133,121,126,135,136, 44,101,131,134,
122,127,136,137, 13, 47, 31, 48, 45, 49, 46, 50, 77,103,102,104,105,107,106,108,
 43,123,100,124,121,126,125,127, 79,138,138,139,140,141,141,142, 52,143,130,144,
110,145,146,147, 80,148,149,150,151,152,153,154, 68,155,146,156,157,158,159,160,
 81,161,162,163,164,165,166,167,  5, 29, 27, 30, 22, 31, 28, 32, 41, 98, 95, 99,
 96,100, 97,101, 29,128, 95,129, 98,130,123,131, 52,130,143,144,110,146,145,147,
 24, 95, 95,109, 92,102,102,114, 47,123,143,155,103,138,148,161, 35,129,143,168,
105,149,169,170, 58,131,171,172,115,162,173,174, 10, 35, 28, 36, 33, 37, 34, 38,
 77,105,102,106,103,107,104,108, 42,129, 97,132,119,133,124,134, 80,149,148,150,
151,153,152,154, 47,143,123,155,103,148,138,161, 82,169,169,175,176,177,177,178,
 67,168,145,179,151,180,181,182, 83,170,173,183,184,185,186,187, 12, 52, 30, 53,
 45, 54, 51, 55, 66,110,109,111,110,112,111,113, 40,130, 99,133,121,135,126,136,
 68,146,155,156,157,159,158,160, 35,143,129,168,105,169,149,170, 67,145,168,179,
151,181,180,182, 63,144,144,188,140,189,189,190, 69,147,172,191,164,192,193,194,
 14, 58, 32, 59, 56, 60, 57, 61, 78,115,114,116,115,117,116,118, 44,131,101,134,
122,136,127,137, 81,162,161,163,164,166,165,167, 58,171,131,172,115,173,162,174,
 83,173,170,183,184,186,185,187, 69,172,147,191,164,193,192,194, 84,174,174,195,
196,197,197,198,  1,  9, 11, 13,  5, 10, 12, 14,  5, 22, 29, 31, 27, 28, 30, 32,
  5, 24, 41, 47, 29, 35, 52, 58,  7, 25, 42, 48, 30, 36, 53, 59,  4, 22, 39, 45,
 22, 33, 45, 56,  6, 23, 40, 46, 28, 34, 51, 57,  6, 25, 43, 49, 31, 37, 54, 60,
  8, 26, 44, 50, 32, 38, 55, 61, 11, 41, 39, 43, 29, 42, 40, 44, 41, 96, 98,100,
 95, 97, 99,101, 29, 95, 98,123,128,129,130,131, 42, 97,119,124,129,132,133,134,
 39, 98,120,121, 98,119,121,122, 43,100,121,125,123,124,126,127, 40, 99,121,126,
130,133,135,136, 44,101,122,127,131,134,136,137,  9, 76, 41, 77, 41, 77, 66, 78,
 24, 92, 95,102, 95,102,109,114, 22, 92, 96,103, 98,105,110,115, 25, 93, 97,104,
 99,106,111,116, 22, 92, 98,105, 96,103,110,115, 25, 93, 99,106, 97,104,111,116,
 23, 93,100,107,100,107,112,117, 26, 94,101,108,101,108,113,118, 13, 77, 43, 79,
 52, 80, 68, 81, 47,103,123,138,143,148,155,161, 31,102,100,138,130,149,146,162,
 48,104,124,139,144,150,156,163, 45,105,121,140,110,151,157,164, 49,107,126,141,
145,152,158,165, 46,106,125,141,146,153,159,166, 50,108,127,142,147,154,160,167,
  5, 41, 29, 52, 24, 47, 35, 58, 29, 98,128,130, 95,123,129,131, 27, 95, 95,143,
 95,143,143,171, 30, 99,129,144,109,155,168,172, 22, 96, 98,110, 92,103,105,115,
 31,100,130,146,102,138,149,162, 28, 97,123,145,102,148,169,173, 32,101,131,147,
114,161,170,174, 12, 66, 40, 68, 35, 67, 63, 69, 52,110,130,146,143,145,144,147,
 30,109, 99,155,129,168,144,172, 53,111,133,156,168,179,188,191, 45,110,121,157,
105,151,140,164, 54,112,135,159,169,181,189,192, 51,111,126,158,149,180,189,193,
 55,113,136,160,170,182,190,194, 10, 77, 42, 80, 47, 82, 67, 83, 35,105,129,149,
143,169,168,170, 28,102, 97,148,123,169,145,173, 36,106,132,150,155,175,179,183,
 33,103,119,151,103,176,151,184, 37,107,133,153,148,177,180,185, 34,104,124,152,
138,177,181,186, 38,108,134,154,161,178,182,187, 14, 78, 44, 81, 58, 83, 69, 84,
 58,115,131,162,171,173,172,174, 32,114,101,161,131,170,147,174, 59,116,134,163,
172,183,191,195, 56,115,122,164,115,184,164,196, 60,117,136,166,173,186,193,197,
 57,116,127,165,162,185,192,197, 61,118,137,167,174,187,194,198,  2, 10, 12, 17,
  6, 15, 16, 18, 10, 33, 35, 37, 28, 34, 36, 38, 12, 35, 66, 67, 40, 63, 68, 69,
 17, 37, 67, 70, 51, 64, 71, 72,  6, 28, 40, 51, 23, 34, 46, 57, 15, 34, 63, 64,
 34, 62, 64, 65, 16, 36, 68, 71, 46, 64, 73, 74, 18, 38, 69, 72, 57, 65, 74, 75,
 13, 47, 45, 49, 31, 48, 46, 50, 77,103,105,107,102,104,106,108, 52,143,110,145,
130,144,146,147, 80,148,151,152,149,150,153,154, 43,123,121,126,100,124,125,127,
 79,138,140,141,138,139,141,142, 68,155,157,158,146,156,159,160, 81,161,164,165,
162,163,166,167, 13, 77, 52, 80, 43, 79, 68, 81, 47,103,143,148,123,138,155,161,
 45,105,110,151,121,140,157,164, 49,107,145,152,126,141,158,165, 31,102,130,149,
100,138,146,162, 48,104,144,150,124,139,156,163, 46,106,146,153,125,141,159,166,
 50,108,147,154,127,142,160,167, 19, 82, 54, 85, 54, 85, 73, 86, 82,176,169,177,
169,177,175,178, 54,169,112,181,135,189,159,192, 85,177,181,199,189,200,201,202,
 54,169,135,189,112,181,159,192, 85,177,189,200,181,199,201,202, 73,175,159,201,
159,201,203,204, 86,178,192,202,192,202,204,205,  7, 42, 30, 53, 25, 48, 36, 59,
 42,119,129,133, 97,124,132,134, 30,129,109,168, 99,144,155,172, 53,133,168,188,
111,156,179,191, 25, 97, 99,111, 93,104,106,116, 48,124,144,156,104,139,150,163,
 36,132,155,179,106,150,175,183, 59,134,172,191,116,163,183,195, 17, 67, 51, 71,
 37, 70, 64, 72, 80,151,149,153,148,152,150,154, 53,168,111,179,133,188,156,191,
 87,180,180,206,180,206,206,207, 49,145,126,158,107,152,141,165, 85,181,189,201,
177,199,200,202, 71,179,158,208,153,206,201,209, 88,182,193,209,185,210,211,212,
 17, 80, 53, 87, 49, 85, 71, 88, 67,151,168,180,145,181,179,182, 51,149,111,180,
126,189,158,193, 71,153,179,206,158,201,208,209, 37,148,133,180,107,177,153,185,
 70,152,188,206,152,199,206,210, 64,150,156,206,141,200,201,211, 72,154,191,207,
165,202,209,212, 20, 83, 55, 88, 60, 89, 74, 90, 83,184,170,185,173,186,183,187,
 55,170,113,182,136,190,160,194, 88,185,182,210,193,211,209,212, 60,173,136,193,
117,186,166,197, 89,186,190,211,186,213,211,214, 74,183,160,209,166,211,204,215,
 90,187,194,212,197,214,215,216,  1, 11,  9, 13,  5, 12, 10, 14, 11, 39, 41, 43,
 29, 40, 42, 44,  9, 41, 76, 77, 41, 66, 77, 78, 13, 43, 77, 79, 52, 68, 80, 81,
  5, 29, 41, 52, 24, 35, 47, 58, 12, 40, 66, 68, 35, 63, 67, 69, 10, 42, 77, 80,
 47, 67, 82, 83, 14, 44, 78, 81, 58, 69, 83, 84,  5, 29, 22, 31, 27, 30, 28, 32,
 41, 98, 96,100, 95, 99, 97,101, 24, 95, 92,102, 95,109,102,114, 47,123,103,138,
143,155,148,161, 29,128, 98,130, 95,129,123,131, 52,130,110,146,143,144,145,147,
 35,129,105,149,143,168,169,170, 58,131,115,162,171,172,173,174,  5, 41, 24, 47,
 29, 52, 35, 58, 29, 98, 95,123,128,130,129,131, 22, 96, 92,103, 98,110,105,115,
 31,100,102,138,130,146,149,162, 27, 95, 95,143, 95,143,143,171, 30, 99,109,155,
129,144,168,172, 28, 97,102,148,123,145,169,173, 32,101,114,161,131,147,170,174,
  7, 42, 25, 48, 30, 53, 36, 59, 42,119, 97,124,129,133,132,134, 25, 97, 93,104,
 99,111,106,116, 48,124,104,139,144,156,150,163, 30,129, 99,144,109,168,155,172,
 53,133,111,156,168,188,179,191, 36,132,106,150,155,179,175,183, 59,134,116,163,
172,191,183,195,  4, 39, 22, 45, 22, 45, 33, 56, 39,120, 98,121, 98,121,119,122,
 22, 98, 92,105, 96,110,103,115, 45,121,105,140,110,157,151,164, 22, 98, 96,110,
 92,105,103,115, 45,121,110,157,105,140,151,164, 33,119,103,151,103,151,176,184,
 56,122,115,164,115,164,184,196,  6, 40, 23, 46, 28, 51, 34, 57, 43,121,100,125,
123,126,124,127, 25, 99, 93,106, 97,111,104,116, 49,126,107,141,145,158,152,165,
 31,130,100,146,102,149,138,162, 54,135,112,159,169,189,181,192, 37,133,107,153,
148,180,177,185, 60,136,117,166,173,193,186,197,  6, 43, 25, 49, 31, 54, 37, 60,
 40,121, 99,126,130,135,133,136, 23,100, 93,107,100,112,107,117, 46,125,106,141,
146,159,153,166, 28,123, 97,145,102,169,148,173, 51,126,111,158,149,189,180,193,
 34,124,104,152,138,181,177,186, 57,127,116,165,162,192,185,197,  8, 44, 26, 50,
 32, 55, 38, 61, 44,122,101,127,131,136,134,137, 26,101, 94,108,101,113,108,118,
 50,127,108,142,147,160,154,167, 32,131,101,147,114,170,161,174, 55,136,113,160,
170,190,182,194, 38,134,108,154,161,182,178,187, 61,137,118,167,174,194,187,198,
  2, 12, 10, 17,  6, 16, 15, 18, 13, 45, 47, 49, 31, 46, 48, 50, 13, 52, 77, 80,
 43, 68, 79, 81, 19, 54, 82, 85, 54, 73, 85, 86,  7, 30, 42, 53, 25, 36, 48, 59,
 17, 51, 67, 71, 37, 64, 70, 72, 17, 53, 80, 87, 49, 71, 85, 88, 20, 55, 83, 88,
 60, 74, 89, 90, 10, 35, 33, 37, 28, 36, 34, 38, 77,105,103,107,102,106,104,108,
 47,143,103,148,123,155,138,161, 82,169,176,177,169,175,177,178, 42,129,119,133,
 97,132,124,134, 80,149,151,153,148,150,152,154, 67,168,151,180,145,179,181,182,
 83,170,184,185,173,183,186,187, 12, 66, 35, 67, 40, 68, 63, 69, 52,110,143,145,
130,146,144,147, 45,110,105,151,121,157,140,164, 54,112,169,181,135,159,189,192,
 30,109,129,168, 99,155,144,172, 53,111,168,179,133,156,188,191, 51,111,149,180,
126,158,189,193, 55,113,170,182,136,160,190,194, 17, 67, 37, 70, 51, 71, 64, 72,
 80,151,148,152,149,153,150,154, 49,145,107,152,126,158,141,165, 85,181,177,199,
189,201,200,202, 53,168,133,188,111,179,156,191, 87,180,180,206,180,206,206,207,
 71,179,153,206,158,208,201,209, 88,182,185,210,193,209,211,212,  6, 40, 28, 51,
 23, 46, 34, 57, 43,121,123,126,100,125,124,127, 31,130,102,149,100,146,138,162,
 54,135,169,189,112,159,181,192, 25, 99, 97,111, 93,106,104,116, 49,126,145,158,
107,141,152,165, 37,133,148,180,107,153,177,185, 60,136,173,193,117,166,186,197,
 15, 63, 34, 64, 34, 64, 62, 65, 79,140,138,141,138,141,139,142, 48,144,104,150,
124,156,139,163, 85,189,177,200,181,201,199,202, 48,144,124,156,104,150,139,163,
 85,189,181,201,177,200,199,202, 70,188,152,206,152,206,199,210, 89,190,186,211,
186,211,213,214, 16, 68, 36, 71, 46, 73, 64, 74, 68,157,155,158,146,159,156,160,
 46,146,106,153,125,159,141,166, 73,159,175,201,159,203,201,204, 36,155,132,179,
106,175,150,183, 71,158,179,208,153,201,206,209, 64,156,150,206,141,201,200,211,
 74,160,183,209,166,204,211,215, 18, 69, 38, 72, 57, 74, 65, 75, 81,164,161,165,
162,166,163,167, 50,147,108,154,127,160,142,167, 86,192,178,202,192,204,202,205,
 59,172,134,191,116,183,163,195, 88,193,182,209,185,211,210,212, 72,191,154,207,
165,209,202,212, 90,194,187,212,197,215,214,216,  2, 13, 13, 19,  7, 17, 17, 20,
 12, 45, 52, 54, 30, 51, 53, 55, 10, 47, 77, 82, 42, 67, 80, 83, 17, 49, 80, 85,
 53, 71, 87, 88,  6, 31, 43, 54, 25, 37, 49, 60, 16, 46, 68, 73, 36, 64, 71, 74,
 15, 48, 79, 85, 48, 70, 85, 89, 18, 50, 81, 86, 59, 72, 88, 90, 12, 52, 45, 54,
 30, 53, 51, 55, 66,110,110,112,109,111,111,113, 35,143,105,169,129,168,149,170,
 67,145,151,181,168,179,180,182, 40,130,121,135, 99,133,126,136, 68,146,157,159,
155,156,158,160, 63,144,140,189,144,188,189,190, 69,147,164,192,172,191,193,194,
 10, 77, 47, 82, 42, 80, 67, 83, 35,105,143,169,129,149,168,170, 33,103,103,176,
119,151,151,184, 37,107,148,177,133,153,180,185, 28,102,123,169, 97,148,145,173,
 36,106,155,175,132,150,179,183, 34,104,138,177,124,152,181,186, 38,108,161,178,
134,154,182,187, 17, 80, 49, 85, 53, 87, 71, 88, 67,151,145,181,168,180,179,182,
 37,148,107,177,133,180,153,185, 70,152,152,199,188,206,206,210, 51,149,126,189,
111,180,158,193, 71,153,158,201,179,206,208,209, 64,150,141,200,156,206,201,211,
 72,154,165,202,191,207,209,212,  6, 43, 31, 54, 25, 49, 37, 60, 40,121,130,135,
 99,126,133,136, 28,123,102,169, 97,145,148,173, 51,126,149,189,111,158,180,193,
 23,100,100,112, 93,107,107,117, 46,125,146,159,106,141,153,166, 34,124,138,181,
104,152,177,186, 57,127,162,192,116,165,185,197, 16, 68, 46, 73, 36, 71, 64, 74,
 68,157,146,159,155,158,156,160, 36,155,106,175,132,179,150,183, 71,158,153,201,
179,208,206,209, 46,146,125,159,106,153,141,166, 73,159,159,203,175,201,201,204,
 64,156,141,201,150,206,200,211, 74,160,166,204,183,209,211,215, 15, 79, 48, 85,
 48, 85, 70, 89, 63,140,144,189,144,189,188,190, 34,138,104,177,124,181,152,186,
 64,141,150,200,156,201,206,211, 34,138,124,181,104,177,152,186, 64,141,156,201,
150,200,206,211, 62,139,139,199,139,199,199,213, 65,142,163,202,163,202,210,214,
 18, 81, 50, 86, 59, 88, 72, 90, 69,164,147,192,172,193,191,194, 38,161,108,178,
134,182,154,187, 72,165,154,202,191,209,207,212, 57,162,127,192,116,185,165,197,
 74,166,160,204,183,211,209,215, 65,163,142,202,163,210,202,214, 75,167,167,205,
195,212,212,216,  3, 14, 14, 20,  8, 18, 18, 21, 14, 56, 58, 60, 32, 57, 59, 61,
 14, 58, 78, 83, 44, 69, 81, 84, 20, 60, 83, 89, 55, 74, 88, 90,  8, 32, 44, 55,
 26, 38, 50, 61, 18, 57, 69, 74, 38, 65, 72, 75, 18, 59, 81, 88, 50, 72, 86, 90,
 21, 61, 84, 90, 61, 75, 90, 91, 14, 58, 56, 60, 32, 59, 57, 61, 78,115,115,117,
114,116,116,118, 58,171,115,173,131,172,162,174, 83,173,184,186,170,183,185,187,
 44,131,122,136,101,134,127,137, 81,162,164,166,161,163,165,167, 69,172,164,193,
147,191,192,194, 84,174,196,197,174,195,197,198, 14, 78, 58, 83, 44, 81, 69, 84,
 58,115,171,173,131,162,172,174, 56,115,115,184,122,164,164,196, 60,117,173,186,
136,166,193,197, 32,114,131,170,101,161,147,174, 59,116,172,183,134,163,191,195,
 57,116,162,185,127,165,192,197, 61,118,174,187,137,167,194,198, 20, 83, 60, 89,
 55, 88, 74, 90, 83,184,173,186,170,185,183,187, 60,173,117,186,136,193,166,197,
 89,186,186,213,190,211,211,214, 55,170,136,190,113,182,160,194, 88,185,193,211,
182,210,209,212, 74,183,166,211,160,209,204,215, 90,187,197,214,194,212,215,216,
  8, 44, 32, 55, 26, 50, 38, 61, 44,122,131,136,101,127,134,137, 32,131,114,170,
101,147,161,174, 55,136,170,190,113,160,182,194, 26,101,101,113, 94,108,108,118,
 50,127,147,160,108,142,154,167, 38,134,161,182,108,154,178,187, 61,137,174,194,
118,167,187,198, 18, 69, 57, 74, 38, 72, 65, 75, 81,164,162,166,161,165,163,167,
 59,172,116,183,134,191,163,195, 88,193,185,211,182,209,210,212, 50,147,127,160,
108,154,142,167, 86,192,192,204,178,202,202,205, 72,191,165,209,154,207,202,212,
 90,194,197,215,187,212,214,216, 18, 81, 59, 88, 50, 86, 72, 90, 69,164,172,193,
147,192,191,194, 57,162,116,185,127,192,165,197, 74,166,183,211,160,204,209,215,
 38,161,134,182,108,178,154,187, 72,165,191,209,154,202,207,212, 65,163,163,210,
142,202,202,214, 75,167,195,212,167,205,212,216, 21, 84, 61, 90, 61, 90, 75, 91,
 84,196,174,197,174,197,195,198, 61,174,118,187,137,194,167,198, 90,197,187,214,
194,215,212,216, 61,174,137,194,118,187,167,198, 90,197,194,215,187,214,212,216,
 75,195,167,212,167,212,205,216, 91,198,198,216,198,216,216,217
};

const unsigned int igraph_i_isographs_3[] =  { 0, 1, 3, 5, 6, 7, 10, 11, 15, 21, 
					       23, 25, 27, 30, 31, 63 };
const unsigned int igraph_i_isographs_3u[] = { 0, 1, 3, 7 };
const unsigned int igraph_i_isographs_4[] = {
   0,    1,    3,    7,    9,   10,   11,   14,   15,   18,   19,   20,   21, 
  22,   23,   27,   29,   30,   31,   54,   55,   63,   73,   75,   76,   77, 
  79,   81,   83,   84,   85,   86,   87,   90,   91,   92,   93,   94,   95, 
  98,   99,  100,  101,  102,  103,  106,  107,  108,  109,  110,  111,  115, 
 116,  117,  118,  119,  122,  123,  124,  125,  126,  127,  219,  220,  221, 
 223,  228,  229,  230,  231,  237,  238,  239,  246,  247,  255,  292,  293, 
 295,  301,  302,  303,  310,  311,  319,  365,  367,  373,  375,  382,  383, 
 511,  585,  587,  591,  593,  594,  595,  596,  597,  598,  599,  601,  602, 
 603,  604,  605,  606,  607,  625,  626,  627,  630,  631,  633,  634,  635, 
 638,  639,  659,  660,  661,  663,  666,  667,  669,  670,  671,  674,  675, 
 678,  679,  683,  686,  687,  694,  695,  703,  729,  731,  732,  733,  735, 
 737,  739,  741,  742,  743,  745,  746,  747,  748,  749,  750,  751,  753, 
 755,  756,  757,  758,  759,  761,  762,  763,  764,  765,  766,  767,  819, 
 822,  823,  826,  827,  830,  831,  875,  876,  877,  879,  883,  885,  886, 
 887,  891,  892,  893,  894,  895,  947,  949,  951,  955,  957,  958,  959, 
1019, 1020, 1021, 1023, 1755, 1757, 1758, 1759, 1782, 1783, 1791, 1883, 1887, 
1907, 1911, 1917, 1918, 1919, 2029, 2031, 2039, 2047, 4095};
const unsigned int igraph_i_isographs_4u[] = { 0, 1, 3, 7, 11, 12, 13, 
					15, 30, 31, 63};

const unsigned int igraph_i_classedges_3[] = { 1,2, 0,2, 2,1, 0,1, 2,0, 1,0 };
const unsigned int igraph_i_classedges_3u[] = { 1,2, 0,2, 0,1 };
const unsigned int igraph_i_classedges_4[] = { 2,3, 1,3, 0,3, 3,2, 1,2, 0,2,
					       3,1, 2,1, 0,1, 3,0, 2,0, 1,0 };
const unsigned int igraph_i_classedges_4u[] = { 2,3, 1,3, 0,3, 1,2, 0,2, 0,1 };

/**
 * \section about_graph_isomorphism
 * 
 * <para>igraph provides four set of functions to deal with graph
 * isomorphism problems.</para>
 * 
 * <para>The \ref igraph_isomorphic() and \ref igraph_subisomorphic()
 * functions make up the first set (in addition with the \ref
 * igraph_permute_vertices() function). These functions choose the
 * algorithm which is best for the supplied input graph. (The choice is
 * not very sophisticated though, see their documentation for
 * details.)</para>
 * 
 * <para>The VF2 graph (and subgraph) isomorphism algorithm is implemented in
 * igraph, these functions are the second set. See \ref
 * igraph_isomorphic_vf2() and \ref igraph_subisomorphic_vf2() for
 * starters.</para>
 * 
 * <para>Functions for the BLISS algorithm constitute the third set, 
 * see \ref igraph_isomorphic_bliss().</para>
 * 
 * <para>Finally, the isomorphism classes of all graphs with three and
 * four vertices are precomputed and stored in igraph, so for these
 * small graphs there is a very simple fast way to decide isomorphism.
 * See \ref igraph_isomorphic_34().
 * </para>
 */

/**
 * \function igraph_isoclass
 * \brief Determine the isomorphism class of a graph with 3 or 4 vertices
 * 
 * </para><para>
 * All graphs with a given number of vertices belong to a number of
 * isomorphism classes, with every graph in a given class being
 * isomorphic to each other.
 * 
 * </para><para>
 * This function gives the isomorphism class (a number) of a
 * graph. Two graphs have the same isomorphism class if and only if
 * they are isomorphic.
 * 
 * </para><para>
 * The first isomorphism class is numbered zero and it is the empty
 * graph, the last isomorphism class is the full graph. The number of
 * isomorphism class for directed graphs with three vertices is 16
 * (between 0 and 15), for undirected graph it is only 4. For graphs
 * with four vertices it is 218 (directed) and 11 (undirected).
 * 
 * \param graph The graph object.
 * \param isoclass Pointer to an integer, the isomorphism class will
 *        be stored here.
 * \return Error code.
 * \sa \ref igraph_isomorphic(), \ref igraph_isoclass_subgraph(),
 * \ref igraph_isoclass_create(), \ref igraph_motifs_randesu().
 * 
 * Because of some limitations this function works only for graphs
 * with three of four vertices.
 * 
 * </para><para>
 * Time complexity: O(|E|), the number of edges in the graph.
 */

int igraph_isoclass(const igraph_t *graph, igraph_integer_t *isoclass) {
  long int e;
  long int no_of_nodes=igraph_vcount(graph);
  long int no_of_edges=igraph_ecount(graph);
  igraph_integer_t from, to;
  unsigned char idx, mul;
  const unsigned int *arr_idx, *arr_code;
  int code=0;

  if (no_of_nodes < 3 || no_of_nodes > 4) {
    IGRAPH_ERROR("Only implemented for graphs with 3 or 4 vertices",
		 IGRAPH_UNIMPLEMENTED);
  }

  if (igraph_is_directed(graph)) {
    if (no_of_nodes==3) {
      arr_idx=igraph_i_isoclass_3_idx;
      arr_code=igraph_i_isoclass2_3;
      mul=3;
    } else {
      arr_idx=igraph_i_isoclass_4_idx;
      arr_code=igraph_i_isoclass2_4;
      mul=4;
    }
  } else {
    if (no_of_nodes==3) {
      arr_idx=igraph_i_isoclass_3u_idx;
      arr_code=igraph_i_isoclass2_3u;
      mul=3;
    } else {
      arr_idx=igraph_i_isoclass_4u_idx;
      arr_code=igraph_i_isoclass2_4u;
      mul=4;
    }
  } 

  for (e=0; e<no_of_edges; e++) {
    igraph_edge(graph, (igraph_integer_t) e, &from, &to);
    idx=(unsigned char) (mul*from+to);
    code |= arr_idx[idx];
  }
  
  *isoclass=(igraph_integer_t) arr_code[code];
  return 0;
}

/**
 * \function igraph_isomorphic 
 * \brief Decides whether two graphs are isomorphic
 * 
 * </para><para>
 * From Wikipedia: The graph isomorphism problem or GI problem is the
 * graph theory problem of determining whether, given two graphs G1
 * and G2, it is possible to permute (or relabel) the vertices of one
 * graph so that it is equal to the other. Such a permutation is
 * called a graph isomorphism.</para>
 * 
 * <para>This function decides which graph isomorphism algorithm to be
 * used based on the input graphs. Right now it does the following:
 * \olist
 * \oli If one graph is directed and the other undirected then an
 *    error is triggered.
 * \oli If the two graphs does not have the same number of vertices
 *    and edges it returns with \c FALSE.
 * \oli Otherwise, if the graphs have three or four vertices then an O(1)
 *    algorithm is used with precomputed data.
 * \oli Otherwise BLISS is used, see \ref igraph_isomorphic_bliss().
 * \endolist 
 * </para>
 * 
 * <para> Please call the VF2 and BLISS functions directly if you need
 * something more sophisticated, e.g. you need the isomorphic mapping.
 * 
 * \param graph1 The first graph.
 * \param graph2 The second graph.
 * \param iso Pointer to a logical variable, will be set to TRUE (1)
 *        if the two graphs are isomorphic, and FALSE (0) otherwise.
 * \return Error code.
 * \sa \ref igraph_isoclass(), \ref igraph_isoclass_subgraph(),
 * \ref igraph_isoclass_create().
 * 
 * Time complexity: exponential.
 */

int igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2,
		      igraph_bool_t *iso) {
  
  long int nodes1=igraph_vcount(graph1), nodes2=igraph_vcount(graph2);
  long int edges1=igraph_ecount(graph1), edges2=igraph_ecount(graph2);
  igraph_bool_t dir1=igraph_is_directed(graph1), dir2=igraph_is_directed(graph2);

  if (dir1 != dir2) {
    IGRAPH_ERROR("Cannot compare directed and undirected graphs", IGRAPH_EINVAL);
  } else if (nodes1 != nodes2 || edges1 != edges2) { 
    *iso=0;
  } else if (nodes1==3 || nodes1==4) {
	igraph_isomorphic_34(graph1, graph2, iso);
  } else {
    igraph_isomorphic_bliss(graph1, graph2, NULL, NULL, iso, 0, 0, /*sh=*/ IGRAPH_BLISS_F, 0, 0);
  }
				
  return 0;
}

/**
 * \function igraph_isomorphic_34
 * Graph isomorphism for 3-4 vertices
 * 
 * This function uses precomputed indices to decide isomorphism
 * problems for graphs with only 3 or 4 vertices.
 * \param graph1 The first input graph.
 * \param graph2 The second input graph. Must have the same
 *   directedness as \p graph1.
 * \param iso Pointer to a boolean, the result is stored here. 
 * \return Error code.
 *
 * Time complexity: O(1).
 */

int igraph_isomorphic_34(const igraph_t *graph1, const igraph_t *graph2, 
			 igraph_bool_t *iso) {

  igraph_integer_t class1, class2;  
  IGRAPH_CHECK(igraph_isoclass(graph1, &class1));
  IGRAPH_CHECK(igraph_isoclass(graph2, &class2));
  *iso= (class1 == class2);
  return 0;
}

/**
 * \function igraph_isoclass_subgraph
 * \brief The isomorphism class of a subgraph of a graph.
 * 
 * </para><para>
 * This function is only implemented for subgraphs with three or four
 * vertices.
 * \param graph The graph object.
 * \param vids A vector containing the vertex ids to be considered as
 *        a subgraph. Each vertex id should be included at most once.
 * \param isoclass Pointer to an integer, this will be set to the
 *        isomorphism class.
 * \return Error code.
 * \sa \ref igraph_isoclass(), \ref igraph_isomorphic(),
 * \ref igraph_isoclass_create().
 * 
 * Time complexity: O((d+n)*n), d is the average degree in the network,
 * and n is the number of vertices in \c vids.
 */

int igraph_isoclass_subgraph(const igraph_t *graph, igraph_vector_t *vids,
			     igraph_integer_t *isoclass) {
  int nodes=(int) igraph_vector_size(vids);
  igraph_bool_t directed=igraph_is_directed(graph);
  igraph_vector_t neis;
  
  unsigned char mul, idx;
  const unsigned int *arr_idx, *arr_code;
  int code=0;
  
  long int i, j, s;

  if (nodes < 3 || nodes > 4) { 
    IGRAPH_ERROR("Only for three- or four-vertex subgraphs",
		 IGRAPH_UNIMPLEMENTED);
  }

  IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);
  
  if (directed) {
    if (nodes==3) {
      arr_idx=igraph_i_isoclass_3_idx;
      arr_code=igraph_i_isoclass2_3;
      mul=3;
    } else {
      arr_idx=igraph_i_isoclass_4_idx;
      arr_code=igraph_i_isoclass2_4;
      mul=4;
    }
  } else {
    if (nodes==3) {
      arr_idx=igraph_i_isoclass_3u_idx;
      arr_code=igraph_i_isoclass2_3u;
      mul=3;
    } else {
      arr_idx=igraph_i_isoclass_4u_idx;
      arr_code=igraph_i_isoclass2_4u;
      mul=4;
    }
  }

  for (i=0; i<nodes; i++) {
    long int from=(long int) VECTOR(*vids)[i];
    igraph_neighbors(graph, &neis, (igraph_integer_t) from, IGRAPH_OUT);
    s=igraph_vector_size(&neis);
    for (j=0; j<s; j++) {
      long int nei=(long int) VECTOR(neis)[j], to;
      if (igraph_vector_search(vids, 0, nei, &to)) {
	idx=(unsigned char) (mul*i+to);
	code |= arr_idx[idx];
      }
    }
  }
  
  *isoclass=(igraph_integer_t) arr_code[code];
  igraph_vector_destroy(&neis);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/**
 * \function igraph_isoclass_create
 * \brief Creates a graph from the given isomorphism class.
 *
 * </para><para>
 * This function is implemented only for graphs with three or four
 * vertices. 
 * \param graph Pointer to an uninitialized graph object.
 * \param size The number of vertices to add to the graph.
 * \param number The isomorphism class.
 * \param directed Logical constant, whether to create a directed
 *        graph. 
 * \return Error code.
 * \sa \ref igraph_isoclass(), 
 * \ref igraph_isoclass_subgraph(),
 * \ref igraph_isomorphic().
 * 
 * Time complexity: O(|V|+|E|), the number of vertices plus the number
 * of edges in the graph to create.
 */

int igraph_isoclass_create(igraph_t *graph, igraph_integer_t size,
			   igraph_integer_t number, igraph_bool_t directed) {
  igraph_vector_t edges;
  const unsigned int *classedges;
  long int power;
  long int code;
  long int pos;

  if (size < 3 || size > 4) {
    IGRAPH_ERROR("Only for graphs with three of four vertices", 
		 IGRAPH_UNIMPLEMENTED);
  }

  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

  if (directed) {
    if (size==3) {
      classedges=igraph_i_classedges_3;

      if (number < 0 || 
	  number >= (int)(sizeof(igraph_i_isographs_3)/sizeof(unsigned int))){
	IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
      }

      code=igraph_i_isographs_3[ (long int) number];
      power=32;
    } else {
      classedges=igraph_i_classedges_4;

      if (number < 0 ||
	  number >= (int)(sizeof(igraph_i_isographs_4)/sizeof(unsigned int))){
	IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
      }

      code=igraph_i_isographs_4[ (long int) number];
      power=2048;
    }
  } else {
    if (size==3) {
      classedges=igraph_i_classedges_3u;

      if (number < 0 ||
	  number >= (int)(sizeof(igraph_i_isographs_3u)/
			  sizeof(unsigned int))){
	IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
      }

      code=igraph_i_isographs_3u[ (long int) number];
      power=4;
    } else {
      classedges=igraph_i_classedges_4u;

      if (number < 0 ||
	  number >= (int)(sizeof(igraph_i_isographs_4u)/
			  sizeof(unsigned int))) {
	IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
      }

      code=igraph_i_isographs_4u[ (long int) number];
      power=32;
    }
  }

  pos=0;
  while (code > 0) {
    if (code >= power) {
      IGRAPH_CHECK(igraph_vector_push_back(&edges, classedges[2*pos]));
      IGRAPH_CHECK(igraph_vector_push_back(&edges, classedges[2*pos+1]));
      code -= power;
    }
    power /= 2;
    pos++;
  }

  IGRAPH_CHECK(igraph_create(graph, &edges, size, directed));
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/**
 * \function igraph_isomorphic_function_vf2
 * The generic VF2 interface
 * 
 * </para><para>
 * This function is an implementation of the VF2 isomorphism algorithm, 
 * see P. Foggia, C. Sansone, M. Vento, An Improved algorithm for
 * matching large graphs, Proc. of the 3rd IAPR-TC-15 International
 * Workshop on Graph-based Representations, Italy, 2001.</para>
 * 
 * <para>For using it you need to define a callback function of type
 * \ref igraph_isohandler_t. This function will be called whenever VF2
 * finds an isomorphism between the two graphs. The mapping between
 * the two graphs will be also provided to this function. If the
 * callback returns a nonzero value then the search is continued,
 * otherwise it stops. The callback function must not destroy the 
 * mapping vectors that are passed to it.
 * \param graph1 The first input graph.
 * \param graph2 The second input graph.
 * \param vertex_color1 An optional color vector for the first graph. If
 *   color vectors are given for both graphs, then the isomorphism is
 *   calculated on the colored graphs; i.e. two vertices can match
 *   only if their color also matches. Supply a null pointer here if
 *   your graphs are not colored.
 * \param vertex_color2 An optional color vector for the second graph. See
 *   the previous argument for explanation.
 * \param edge_color1 An optional edge color vector for the first
 *   graph. The matching edges in the two graphs must have matching
 *   colors as well. Supply a null pointer here if your graphs are not 
 *   edge-colored.
 * \param edge_color2 The edge color vector for the second graph.
 * \param map12 Pointer to an initialized vector or \c NULL. If not \c
 *   NULL and the supplied graphs are isomorphic then the permutation
 *   taking \p graph1 to \p graph is stored here. If not \c NULL and the
 *   graphs are not isomorphic then a zero-length vector is returned.
 * \param map21 This is the same as \p map12, but for the permutation
 *   taking \p graph2 to \p graph1.
 * \param isohandler_fn The callback function to be called if an
 *   isomorphism is found. See also \ref igraph_isohandler_t.
 * \param node_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two nodes are compatible.
 * \param edge_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two edges are compatible.
 * \param arg Extra argument to supply to functions \p isohandler_fn, \p
 *   node_compat_fn and \p edge_compat_fn. 
 * \return Error code.
 * 
 * Time complexity: exponential.
 */
  
int igraph_isomorphic_function_vf2(const igraph_t *graph1, const igraph_t *graph2, 
				   const igraph_vector_int_t *vertex_color1,
				   const igraph_vector_int_t *vertex_color2,
				   const igraph_vector_int_t *edge_color1,
				   const igraph_vector_int_t *edge_color2,
				   igraph_vector_t *map12,
				   igraph_vector_t *map21,
				   igraph_isohandler_t *isohandler_fn,
				   igraph_isocompat_t *node_compat_fn,
				   igraph_isocompat_t *edge_compat_fn,
				   void *arg) {
  
  long int no_of_nodes=igraph_vcount(graph1);
  long int no_of_edges=igraph_ecount(graph1);
  igraph_vector_t mycore_1, mycore_2, *core_1=&mycore_1, *core_2=&mycore_2;
  igraph_vector_t in_1, in_2, out_1, out_2;
  long int in_1_size=0, in_2_size=0, out_1_size=0, out_2_size=0;
  igraph_vector_t *inneis_1, *inneis_2, *outneis_1, *outneis_2;
  long int matched_nodes=0;
  long int depth;
  long int cand1, cand2;
  long int last1, last2;
  igraph_stack_t path;
  igraph_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
  igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;

  if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
    IGRAPH_ERROR("Cannot compare directed and undirected graphs",
		 IGRAPH_EINVAL);
  }

  if ( (vertex_color1 && !vertex_color2) || (!vertex_color1 && vertex_color2) ) {
    IGRAPH_WARNING("Only one graph is vertex-colored, vertex colors will be ignored");
    vertex_color1=vertex_color2=0;
  }

  if ( (edge_color1 && !edge_color2) || (!edge_color1 && edge_color2)) {
    IGRAPH_WARNING("Only one graph is edge-colored, edge colors will be ignored");
    edge_color1 = edge_color2 = 0;
  }

  if (vertex_color1) {
    if (igraph_vector_int_size(vertex_color1) != no_of_nodes ||
	igraph_vector_int_size(vertex_color2) != no_of_nodes) {
      IGRAPH_ERROR("Invalid vertex color vector length", IGRAPH_EINVAL);
    }
  }

  if (edge_color1) {
    if (igraph_vector_int_size(edge_color1) != no_of_edges ||
	igraph_vector_int_size(edge_color2) != no_of_edges) {
      IGRAPH_ERROR("Invalid edge color vector length", IGRAPH_EINVAL);
    }
  }

  if (no_of_nodes != igraph_vcount(graph2) ||
      no_of_edges != igraph_ecount(graph2)) {
    return 0;
  }
  
  /* Check color distribution */
  if (vertex_color1) {
    int ret=0;
    igraph_vector_int_t tmp1, tmp2;
    IGRAPH_CHECK(igraph_vector_int_copy(&tmp1, vertex_color1));
    IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp1);
    IGRAPH_CHECK(igraph_vector_int_copy(&tmp2, vertex_color2));
    IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp2);
    igraph_vector_int_sort(&tmp1);
    igraph_vector_int_sort(&tmp2);
    ret= !igraph_vector_int_all_e(&tmp1, &tmp2);
    igraph_vector_int_destroy(&tmp1);
    igraph_vector_int_destroy(&tmp2);
    IGRAPH_FINALLY_CLEAN(2);
    if (ret) { return 0; }
  }

  /* Check edge color distribution */
  if (edge_color1) {
    int ret=0;
    igraph_vector_int_t tmp1, tmp2;
    IGRAPH_CHECK(igraph_vector_int_copy(&tmp1, edge_color1));
    IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp1);
    IGRAPH_CHECK(igraph_vector_int_copy(&tmp2, edge_color2));
    IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp2);
    igraph_vector_int_sort(&tmp1);
    igraph_vector_int_sort(&tmp2);
    ret= !igraph_vector_int_all_e(&tmp1, &tmp2);
    igraph_vector_int_destroy(&tmp1);
    igraph_vector_int_destroy(&tmp2);
    IGRAPH_FINALLY_CLEAN(2);
    if (ret) { return 0; }
  }

  if (map12) {
    core_1=map12;
    IGRAPH_CHECK(igraph_vector_resize(core_1, no_of_nodes));
  } else {
    IGRAPH_VECTOR_INIT_FINALLY(core_1, no_of_nodes);
  }
  igraph_vector_fill(core_1, -1);
  if (map21) {
    core_2=map21;
    IGRAPH_CHECK(igraph_vector_resize(core_2, no_of_nodes));
    igraph_vector_null(core_2);
  } else {
    IGRAPH_VECTOR_INIT_FINALLY(core_2, no_of_nodes);
  }
  igraph_vector_fill(core_2, -1);
  
  IGRAPH_VECTOR_INIT_FINALLY(&in_1, no_of_nodes);
  IGRAPH_VECTOR_INIT_FINALLY(&in_2, no_of_nodes);
  IGRAPH_VECTOR_INIT_FINALLY(&out_1, no_of_nodes);
  IGRAPH_VECTOR_INIT_FINALLY(&out_2, no_of_nodes);
  IGRAPH_CHECK(igraph_stack_init(&path, 0));
  IGRAPH_FINALLY(igraph_stack_destroy, &path);
  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN, 
					  IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj1);
  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT, 
					  IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj1);
  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN, 
					  IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj2);
  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT, 
					  IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj2);
  IGRAPH_VECTOR_INIT_FINALLY(&indeg1, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&indeg2, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&outdeg1, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&outdeg2, 0);

  IGRAPH_CHECK(igraph_stack_reserve(&path, no_of_nodes*2));
  IGRAPH_CHECK(igraph_degree(graph1, &indeg1, igraph_vss_all(), 
			     IGRAPH_IN, IGRAPH_LOOPS));
  IGRAPH_CHECK(igraph_degree(graph2, &indeg2, igraph_vss_all(), 
			     IGRAPH_IN, IGRAPH_LOOPS));
  IGRAPH_CHECK(igraph_degree(graph1, &outdeg1, igraph_vss_all(), 
			     IGRAPH_OUT, IGRAPH_LOOPS));
  IGRAPH_CHECK(igraph_degree(graph2, &outdeg2, igraph_vss_all(), 
			     IGRAPH_OUT, IGRAPH_LOOPS));

  depth=0; last1=-1; last2=-1;
  while (depth >= 0) {
    long int i;
    
    IGRAPH_ALLOW_INTERRUPTION();

    cand1=-1; cand2=-1;
    /* Search for the next pair to try */
    if ((in_1_size != in_2_size) ||
	(out_1_size != out_2_size)) {
      /* step back, nothing to do */
    } else if (out_1_size > 0 && out_2_size > 0) {
      /**************************************************************/
      /* cand2, search not always needed */
      if (last2 >= 0) {
	cand2=last2;
      } else {
	i=0;
	while (cand2<0 && i<no_of_nodes) {
	  if (VECTOR(out_2)[i]>0 && VECTOR(*core_2)[i] < 0) {
	    cand2=i;
	  }
	  i++;
	}
      }
      /* search for cand1 now, it should be bigger than last1 */
      i=last1+1;
      while (cand1<0 && i<no_of_nodes) {
	if (VECTOR(out_1)[i]>0 && VECTOR(*core_1)[i] < 0) {
	  cand1=i;
	}
	i++;
      }
    } else if (in_1_size > 0 && in_2_size > 0) {
      /**************************************************************/
      /* cand2, search not always needed */
      if (last2 >= 0) {
	cand2=last2;
      } else {
	i=0;
	while (cand2<0 && i<no_of_nodes) {
	  if (VECTOR(in_2)[i]>0 && VECTOR(*core_2)[i] < 0) {
	    cand2=i;
	  }
	  i++;
	}
      }
      /* search for cand1 now, should be bigger than last1 */
      i=last1+1;
      while (cand1<0 && i<no_of_nodes) {
	if (VECTOR(in_1)[i]>0 && VECTOR(*core_1)[i] < 0) {
	  cand1=i;
	}
	i++;
      }
    } else {
      /**************************************************************/
      /* cand2, search not always needed */
      if (last2 >= 0) {
	cand2=last2;
      } else {
	i=0;
	while (cand2<0 && i<no_of_nodes) {
	  if (VECTOR(*core_2)[i] < 0) { 
	    cand2=i;
	  }
	  i++;
	}
      }
      /* search for cand1, should be bigger than last1 */
      i=last1+1;
      while (cand1<0 && i<no_of_nodes) {
	if (VECTOR(*core_1)[i] < 0) {
	  cand1=i;
	}
	i++;
      }
    }
        
    /* Ok, we have cand1, cand2 as candidates. Or not? */
    if (cand1<0 || cand2<0) {
      /**************************************************************/
      /* dead end, step back, if possible. Otherwise we'll terminate */
      if (depth >= 1) {
	last2=(long int) igraph_stack_pop(&path);
	last1=(long int) igraph_stack_pop(&path);
	matched_nodes -= 1;
	VECTOR(*core_1)[last1]=-1;
	VECTOR(*core_2)[last2]=-1;
	
	if (VECTOR(in_1)[last1] != 0) {
	  in_1_size += 1;
	}
	if (VECTOR(out_1)[last1] != 0) {
	  out_1_size += 1;
	}
	if (VECTOR(in_2)[last2] != 0) {
	  in_2_size += 1;
	} 
	if (VECTOR(out_2)[last2] != 0) {
	  out_2_size += 1;
	}
	
	inneis_1=igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) last1);
	for (i=0; i<igraph_vector_size(inneis_1); i++) {
	  long int node=(long int) VECTOR(*inneis_1)[i];
	  if (VECTOR(in_1)[node] == depth) {
	    VECTOR(in_1)[node]=0;
	    in_1_size -= 1;
	  }
	}
	outneis_1=igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) last1);
	for (i=0; i<igraph_vector_size(outneis_1); i++) {
	  long int node=(long int) VECTOR(*outneis_1)[i];
	  if (VECTOR(out_1)[node] == depth) {
	    VECTOR(out_1)[node]=0;
	    out_1_size -= 1;
	  }
	}
	inneis_2=igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) last2);
	for (i=0; i<igraph_vector_size(inneis_2); i++) {
	  long int node=(long int) VECTOR(*inneis_2)[i];
	  if (VECTOR(in_2)[node] == depth) {
	    VECTOR(in_2)[node]=0;
	    in_2_size -= 1;
	  }
	}
	outneis_2=igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) last2);
	for (i=0; i<igraph_vector_size(outneis_2); i++) {
	  long int node=(long int) VECTOR(*outneis_2)[i];
	  if (VECTOR(out_2)[node] == depth) {
	    VECTOR(out_2)[node]=0;
	    out_2_size -= 1;
	  }
	}
	
      }	/* end of stepping back */
      
      depth -= 1;

    } else {
      /**************************************************************/
      /* step forward if worth, check if worth first */
      long int xin1=0, xin2=0, xout1=0, xout2=0;
      igraph_bool_t end=0;
      inneis_1=igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
      outneis_1=igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
      inneis_2=igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
      outneis_2=igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
      if (VECTOR(indeg1)[cand1] != VECTOR(indeg2)[cand2] ||
	  VECTOR(outdeg1)[cand1] != VECTOR(outdeg2)[cand2]) {
	end=1;
      }
      if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
	end=1;
      }
      if (node_compat_fn && !node_compat_fn(graph1, graph2, 
					    (igraph_integer_t) cand1, 
					    (igraph_integer_t) cand2, arg)) {
	end=1;
      }

      for (i=0; !end && i<igraph_vector_size(inneis_1); i++) {
	long int node=(long int) VECTOR(*inneis_1)[i];
	if (VECTOR(*core_1)[node]>=0) {
	  long int node2=(long int) VECTOR(*core_1)[node];
	  /* check if there is a node2->cand2 edge */
	  if (!igraph_vector_binsearch2(inneis_2, node2)) {
	    end=1;
	  } else if (edge_color1 || edge_compat_fn) {
	    igraph_integer_t eid1, eid2;
	    igraph_get_eid(graph1, &eid1, (igraph_integer_t) node, 
			   (igraph_integer_t) cand1, /*directed=*/ 1, 
			   /*error=*/ 1);
	    igraph_get_eid(graph2, &eid2, (igraph_integer_t) node2, 
			   (igraph_integer_t) cand2, /*directed=*/ 1,
			   /*error=*/ 1);
	    if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
		VECTOR(*edge_color2)[(long int)eid2]) {
	      end=1;
	    }
	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
						  eid1, eid2, arg)) {
	      end=1;
	    }
	  }
	} else { 
	  if (VECTOR(in_1)[node] != 0) {
	    xin1++;
	  }
	  if (VECTOR(out_1)[node] != 0) {
	    xout1++;
	  }
	}
      }
      for (i=0; !end && i<igraph_vector_size(outneis_1); i++) {
	long int node=(long int) VECTOR(*outneis_1)[i];
	if (VECTOR(*core_1)[node]>=0) {
	  long int node2=(long int) VECTOR(*core_1)[node];
	  /* check if there is a cand2->node2 edge */
	  if (!igraph_vector_binsearch2(outneis_2, node2)) {
	    end=1;
	  } else if (edge_color1 || edge_compat_fn) {
	    igraph_integer_t eid1, eid2;
	    igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1, 
			   (igraph_integer_t) node, /*directed=*/ 1, 
			   /*error=*/ 1);
	    igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2, 
			   (igraph_integer_t) node2, /*directed=*/ 1,
			   /*error=*/ 1);
	    if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] != 
		VECTOR(*edge_color2)[(long int)eid2]) {
	      end=1;
	    }
	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, 
						  eid1, eid2, arg)) {
	      end=1;
	    }
	  }
	} else {
	  if (VECTOR(in_1)[node] != 0) {
	    xin1++;
	  }
	  if (VECTOR(out_1)[node] != 0) {
	    xout1++;
	  }
	}
      }      
      for (i=0; !end && i<igraph_vector_size(inneis_2); i++) {
	long int node=(long int) VECTOR(*inneis_2)[i];
	if (VECTOR(*core_2)[node]>=0) {
	  long int node2=(long int) VECTOR(*core_2)[node];
	  /* check if there is a node2->cand1 edge */
	  if (!igraph_vector_binsearch2(inneis_1, node2)) {
	    end=1;
	  } else if (edge_color1 || edge_compat_fn) {
	    igraph_integer_t eid1, eid2;
	    igraph_get_eid(graph1, &eid1, (igraph_integer_t) node2, 
			   (igraph_integer_t) cand1, /*directed=*/ 1, 
			   /*error=*/ 1);
	    igraph_get_eid(graph2, &eid2, (igraph_integer_t) node, 
			   (igraph_integer_t) cand2, /*directed=*/ 1,
			   /*error=*/ 1);
	    if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] != 
		VECTOR(*edge_color2)[(long int)eid2]) {
	      end=1;
	    }
	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, 
						  eid1, eid2, arg)) {
	      end=1;
	    }
	  }
	} else { 
	  if (VECTOR(in_2)[node] != 0) {
	    xin2++;
	  }
	  if (VECTOR(out_2)[node] != 0) {
	    xout2++;
	  }
	}
      }      
      for (i=0; !end && i<igraph_vector_size(outneis_2); i++) {
	long int node=(long int) VECTOR(*outneis_2)[i];
	if (VECTOR(*core_2)[node] >= 0) {
	  long int node2=(long int) VECTOR(*core_2)[node];
	  /* check if there is a cand1->node2 edge */
	  if (!igraph_vector_binsearch2(outneis_1, node2)) {
	    end=1;
	  } else if (edge_color1 || edge_compat_fn) {
	    igraph_integer_t eid1, eid2;
	    igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1, 
			   (igraph_integer_t) node2, /*directed=*/ 1, 
			   /*error=*/ 1);
	    igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2, 
			   (igraph_integer_t) node, /*directed=*/ 1, 
			   /*error=*/ 1);
	    if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] != 
		VECTOR(*edge_color2)[(long int)eid2]) {
	      end=1;
	    }
	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, 
						  eid1, eid2, arg)) {
	      end=1;
	    }
	  }
	} else {
	  if (VECTOR(in_2)[node] != 0) {
	    xin2++;
	  }
	  if (VECTOR(out_2)[node] != 0) {
	    xout2++;
	  }
	}
      }      
      
      if (!end && (xin1==xin2 && xout1==xout2)) {
	/* Ok, we add the (cand1, cand2) pair to the mapping */
	depth += 1;
	IGRAPH_CHECK(igraph_stack_push(&path, cand1));
	IGRAPH_CHECK(igraph_stack_push(&path, cand2));
	matched_nodes += 1;
	VECTOR(*core_1)[cand1]=cand2;
	VECTOR(*core_2)[cand2]=cand1;
	
	/* update in_*, out_* */
	if (VECTOR(in_1)[cand1] != 0) {
	  in_1_size -= 1;
	}
	if (VECTOR(out_1)[cand1] != 0) {
	  out_1_size -= 1;
	}
	if (VECTOR(in_2)[cand2] != 0) {
	  in_2_size -= 1;
	}
	if (VECTOR(out_2)[cand2] != 0) {
	  out_2_size -= 1;
	}
	
	inneis_1=igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
	for (i=0; i<igraph_vector_size(inneis_1); i++) {
	  long int node=(long int) VECTOR(*inneis_1)[i];
	  if (VECTOR(in_1)[node]==0 && VECTOR(*core_1)[node] < 0) {
	    VECTOR(in_1)[node]=depth;
	    in_1_size += 1;
	  }
	}
	outneis_1=igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
	for (i=0; i<igraph_vector_size(outneis_1); i++) {
	  long int node=(long int) VECTOR(*outneis_1)[i];
	  if (VECTOR(out_1)[node]==0 && VECTOR(*core_1)[node] < 0) {
	    VECTOR(out_1)[node]=depth;
	    out_1_size += 1;
	  }
	}
	inneis_2=igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
	for (i=0; i<igraph_vector_size(inneis_2); i++) {
	  long int node=(long int) VECTOR(*inneis_2)[i];
	  if (VECTOR(in_2)[node]==0 && VECTOR(*core_2)[node] < 0) {
	    VECTOR(in_2)[node]=depth;
	    in_2_size += 1;
	  }
	}
	outneis_2=igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
	for (i=0; i<igraph_vector_size(outneis_2); i++) {
	  long int node=(long int) VECTOR(*outneis_2)[i];
	  if (VECTOR(out_2)[node]==0 && VECTOR(*core_2)[node] < 0) {
	    VECTOR(out_2)[node]=depth;
	    out_2_size += 1;
	  }
	}
	last1=-1; last2=-1;    	      /* this the first time here */
      } else {
	last1=cand1;
	last2=cand2;
      }
      
    }
    
    if (matched_nodes==no_of_nodes && isohandler_fn) {
      if (!isohandler_fn(core_1, core_2, arg)) {
	break;
      }
    }
  }

  igraph_vector_destroy(&outdeg2);
  igraph_vector_destroy(&outdeg1);
  igraph_vector_destroy(&indeg2);
  igraph_vector_destroy(&indeg1);
  igraph_lazy_adjlist_destroy(&outadj2);
  igraph_lazy_adjlist_destroy(&inadj2);
  igraph_lazy_adjlist_destroy(&outadj1);
  igraph_lazy_adjlist_destroy(&inadj1);  
  igraph_stack_destroy(&path);
  igraph_vector_destroy(&out_2);
  igraph_vector_destroy(&out_1);
  igraph_vector_destroy(&in_2);
  igraph_vector_destroy(&in_1);
  IGRAPH_FINALLY_CLEAN(13);
  if (!map21) {
    igraph_vector_destroy(core_2);
    IGRAPH_FINALLY_CLEAN(1);
  } 
  if (!map12) { 
    igraph_vector_destroy(core_1);
    IGRAPH_FINALLY_CLEAN(1);
  }

  return 0;
}

typedef struct {
  igraph_isocompat_t *node_compat_fn, *edge_compat_fn;
  void *arg, *carg;
} igraph_i_iso_cb_data_t;

igraph_bool_t igraph_i_isocompat_node_cb(const igraph_t *graph1, 
					 const igraph_t *graph2, 
					 const igraph_integer_t g1_num,
					 const igraph_integer_t g2_num,
					 void *arg) {
  igraph_i_iso_cb_data_t *data=arg;
  return data->node_compat_fn(graph1, graph2, g1_num, g2_num, data->carg);
}

igraph_bool_t igraph_i_isocompat_edge_cb(const igraph_t *graph1, 
					 const igraph_t *graph2,
					 const igraph_integer_t g1_num,
					 const igraph_integer_t g2_num,
					 void *arg) {
  igraph_i_iso_cb_data_t *data=arg;
  return data->edge_compat_fn(graph1, graph2, g1_num, g2_num, data->carg);
}

igraph_bool_t igraph_i_isomorphic_vf2(igraph_vector_t *map12,
				      igraph_vector_t *map21,
				      void *arg) {
  igraph_i_iso_cb_data_t *data = arg;
  igraph_bool_t *iso = data->arg;
  IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
  *iso = 1;
  return 0;			/* don't need to continue */
}

/**
 * \function igraph_isomorphic_vf2
 * \brief Isomorphism via VF2
 * 
 * </para><para>
 * This function performs the VF2 algorithm via calling \ref
 * igraph_isomorphic_function_vf2().
 * 
 * </para><para> Note that this function cannot be used for
 * deciding subgraph isomorphism, use \ref igraph_subisomorphic_vf2()
 * for that.
 * \param graph1 The first graph, may be directed or undirected.
 * \param graph2 The second graph. It must have the same directedness
 *    as \p graph1, otherwise an error is reported.
 * \param vertex_color1 An optional color vector for the first graph. If
 *   color vectors are given for both graphs, then the isomorphism is
 *   calculated on the colored graphs; i.e. two vertices can match
 *   only if their color also matches. Supply a null pointer here if
 *   your graphs are not colored.
 * \param vertex_color2 An optional color vector for the second graph. See
 *   the previous argument for explanation.
 * \param edge_color1 An optional edge color vector for the first
 *   graph. The matching edges in the two graphs must have matching
 *   colors as well. Supply a null pointer here if your graphs are not 
 *   edge-colored.
 * \param edge_color2 The edge color vector for the second graph.
 * \param iso Pointer to a logical constant, the result of the
 *    algorithm will be placed here.
 * \param map12 Pointer to an initialized vector or a NULL pointer. If not 
 *    a NULL pointer then the mapping from \p graph1 to \p graph2 is
 *    stored here. If the graphs are not isomorphic then the vector is
 *    cleared (ie. has zero elements).
 * \param map21 Pointer to an initialized vector or a NULL pointer. If not
 *    a NULL pointer then the mapping from \p graph2 to \p graph1 is
 *    stored here. If the graphs are not isomorphic then the vector is
 *    cleared (ie. has zero elements).
 * \param node_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two nodes are compatible.
 * \param edge_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two edges are compatible.
 * \param arg Extra argument to supply to functions \p node_compat_fn
 *   and \p edge_compat_fn. 
 * \return Error code.
 * 
 * \sa \ref igraph_subisomorphic_vf2(),
 * \ref igraph_count_isomorphisms_vf2(), 
 * \ref igraph_get_isomorphisms_vf2(),
 * 
 * Time complexity: exponential, what did you expect?
 * 
 * \example examples/simple/igraph_isomorphic_vf2.c
 */

int igraph_isomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2, 
			  const igraph_vector_int_t *vertex_color1,
			  const igraph_vector_int_t *vertex_color2,
			  const igraph_vector_int_t *edge_color1,
			  const igraph_vector_int_t *edge_color2,
			  igraph_bool_t *iso, igraph_vector_t *map12, 
			  igraph_vector_t *map21,
			  igraph_isocompat_t *node_compat_fn,
			  igraph_isocompat_t *edge_compat_fn,
			  void *arg) {

  igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, iso, arg };
  igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
  igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
  *iso=0;
  IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2, 
					      vertex_color1, vertex_color2,
					      edge_color1, edge_color2,
					      map12, map21,
					      (igraph_isohandler_t*)
					      igraph_i_isomorphic_vf2,
					      ncb, ecb, &data));
  if (! *iso) {
    if (map12) { igraph_vector_clear(map12); }
    if (map21) { igraph_vector_clear(map21); }
  }
  return 0;
}

igraph_bool_t igraph_i_count_isomorphisms_vf2(const igraph_vector_t *map12,
					      const igraph_vector_t *map21,
					      void *arg) {
  igraph_i_iso_cb_data_t *data = arg;
  igraph_integer_t *count = data->arg;
  IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
  *count += 1;
  return 1;			/* always continue */
}

/**
 * \function igraph_count_isomorphisms_vf2
 * Number of isomorphisms via VF2
 * 
 * This function counts the number of isomorphic mappings between two
 * graphs. It uses the generic \ref igraph_isomorphic_function_vf2()
 * function. 
 * \param graph1 The first input graph, may be directed or undirected.
 * \param graph2 The second input graph, it must have the same
 *   directedness as \p graph1, or an error will be reported.
 * \param vertex_color1 An optional color vector for the first graph. If
 *   color vectors are given for both graphs, then the isomorphism is
 *   calculated on the colored graphs; i.e. two vertices can match
 *   only if their color also matches. Supply a null pointer here if
 *   your graphs are not colored.
 * \param vertex_color2 An optional color vector for the second graph. See
 *   the previous argument for explanation.
 * \param edge_color1 An optional edge color vector for the first
 *   graph. The matching edges in the two graphs must have matching
 *   colors as well. Supply a null pointer here if your graphs are not 
 *   edge-colored.
 * \param edge_color2 The edge color vector for the second graph.
 * \param count Point to an integer, the result will be stored here.
 * \param node_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two nodes are compatible.
 * \param edge_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two edges are compatible.
 * \param arg Extra argument to supply to functions \p node_compat_fn and
 *   \p edge_compat_fn.
 * \return Error code.
 * 
 * Time complexity: exponential.
 */

int igraph_count_isomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2, 
				  const igraph_vector_int_t *vertex_color1,
				  const igraph_vector_int_t *vertex_color2,
				  const igraph_vector_int_t *edge_color1,
				  const igraph_vector_int_t *edge_color2,
				  igraph_integer_t *count,
				  igraph_isocompat_t *node_compat_fn,
				  igraph_isocompat_t *edge_compat_fn,
				  void *arg) {

  igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, 
				  count, arg };
  igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
  igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
  *count=0;
  IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2, 
					      vertex_color1, vertex_color2, 
					      edge_color1, edge_color2,
					      0, 0,
					      (igraph_isohandler_t*)
					      igraph_i_count_isomorphisms_vf2,
					      ncb, ecb, &data));
  return 0;
}

void igraph_i_get_isomorphisms_free(igraph_vector_ptr_t *data) {
  long int i, n=igraph_vector_ptr_size(data);
  for (i=0; i<n; i++) {
    igraph_vector_t *vec=VECTOR(*data)[i];
    igraph_vector_destroy(vec);
    igraph_free(vec);
  }
}

igraph_bool_t igraph_i_get_isomorphisms_vf2(const igraph_vector_t *map12,
					    const igraph_vector_t *map21,
					    void *arg) {

  igraph_i_iso_cb_data_t *data=arg;
  igraph_vector_ptr_t *ptrvector=data->arg;
  igraph_vector_t *newvector=igraph_Calloc(1, igraph_vector_t);
  IGRAPH_UNUSED(map12);
  if (!newvector) { 
    igraph_error("Out of memory", __FILE__, __LINE__, IGRAPH_ENOMEM);
    return 0;			/* stop right here */
  }
  IGRAPH_FINALLY(igraph_free, newvector);
  IGRAPH_CHECK(igraph_vector_copy(newvector, map21));
  IGRAPH_FINALLY(igraph_vector_destroy, newvector);
  IGRAPH_CHECK(igraph_vector_ptr_push_back(ptrvector, newvector));
  IGRAPH_FINALLY_CLEAN(2);
  
  return 1;			/* continue finding subisomorphisms */
}

/** 
 * \function igraph_get_isomorphisms_vf2
 * Collect the isomorphic mappings
 * 
 * This function finds all the isomorphic mappings between two
 * graphs. It uses the \ref igraph_isomorphic_function_vf2()
 * function. Call the function with the same graph as \p graph1 and \p
 * graph2 to get automorphisms.
 * \param graph1 The first input graph, may be directed or undirected.
 * \param graph2 The second input graph, it must have the same
 *   directedness as \p graph1, or an error will be reported.
 * \param vertex_color1 An optional color vector for the first graph. If
 *   color vectors are given for both graphs, then the isomorphism is
 *   calculated on the colored graphs; i.e. two vertices can match
 *   only if their color also matches. Supply a null pointer here if
 *   your graphs are not colored.
 * \param vertex_color2 An optional color vector for the second graph. See
 *   the previous argument for explanation.
 * \param edge_color1 An optional edge color vector for the first
 *   graph. The matching edges in the two graphs must have matching
 *   colors as well. Supply a null pointer here if your graphs are not 
 *   edge-colored.
 * \param edge_color2 The edge color vector for the second graph.
 * \param maps Pointer vector. On return it is empty if the input graphs
 *   are no isomorphic. Otherwise it contains pointers to
 *   <type>igraph_vector_t</type> objects, each vector is an
 *   isomorphic mapping of \p graph2 to \p graph1. Please note that
 *   you need to 1) Destroy the vectors via \ref
 *   igraph_vector_destroy(), 2) free them via
 *   <function>free()</function> and then 3) call \ref
 *   igraph_vector_ptr_destroy() on the pointer vector to deallocate all
 *   memory when \p maps is no longer needed.
 * \param node_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two nodes are compatible.
 * \param edge_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two edges are compatible.
 * \param arg Extra argument to supply to functions \p node_compat_fn
 *   and \p edge_compat_fn. 
 * \return Error code.
 * 
 * Time complexity: exponential.
 */
 
int igraph_get_isomorphisms_vf2(const igraph_t *graph1,
				const igraph_t *graph2,
				const igraph_vector_int_t *vertex_color1,
				const igraph_vector_int_t *vertex_color2,
				const igraph_vector_int_t *edge_color1,
				const igraph_vector_int_t *edge_color2,
				igraph_vector_ptr_t *maps,
				igraph_isocompat_t *node_compat_fn,
				igraph_isocompat_t *edge_compat_fn,
				void *arg) {
  
  igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, maps, arg };
  igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
  igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;

  igraph_vector_ptr_clear(maps);
  IGRAPH_FINALLY(igraph_i_get_isomorphisms_free, maps);
  IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2, 
					      vertex_color1, vertex_color2, 
					      edge_color1, edge_color2,
					      0, 0,
					      (igraph_isohandler_t*)
					      igraph_i_get_isomorphisms_vf2,
					      ncb, ecb, &data));
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}


/**
 * \function igraph_subisomorphic
 * Decide subgraph isomorphism
 * 
 * Check whether \p graph2 is isomorphic to a subgraph of \p graph1.
 * Currently this function just calls \ref igraph_subisomorphic_vf2()
 * for all graphs.
 * \param graph1 The first input graph, may be directed or
 *   undirected. This is supposed to be the bigger graph.
 * \param graph2 The second input graph, it must have the same
 *   directedness as \p graph2, or an error is triggered. This is
 *   supposed to be the smaller graph.
 * \param iso Pointer to a boolean, the result is stored here.
 * \return Error code.
 *
 * Time complexity: exponential. 
 */

int igraph_subisomorphic(const igraph_t *graph1, const igraph_t *graph2,
			 igraph_bool_t *iso) {

  return igraph_subisomorphic_vf2(graph1, graph2, 0, 0, 0, 0, iso, 0, 0, 0, 0, 0);
}

/**
 * \function igraph_subisomorphic_function_vf2
 * Generic VF2 function for subgraph isomorphism problems
 * 
 * This function is the pair of \ref igraph_isomorphic_function_vf2(),
 * for subgraph isomorphism problems. It searches for subgraphs of \p
 * graph1 which are isomorphic to \p graph2. When it founds an
 * isomorphic mapping it calls the supplied callback \p isohandler_fn.
 * The mapping (and its inverse) and the additional \p arg argument
 * are supplied to the callback.
 * \param graph1 The first input graph, may be directed or
 *    undirected. This is supposed to be the larger graph.
 * \param graph2 The second input graph, it must have the same
 *    directedness as \p graph1. This is supposed to be the smaller
 *    graph.
 * \param vertex_color1 An optional color vector for the first graph. If
 *   color vectors are given for both graphs, then the subgraph isomorphism is
 *   calculated on the colored graphs; i.e. two vertices can match
 *   only if their color also matches. Supply a null pointer here if
 *   your graphs are not colored.
 * \param vertex_color2 An optional color vector for the second graph. See
 *   the previous argument for explanation.
 * \param edge_color1 An optional edge color vector for the first
 *   graph. The matching edges in the two graphs must have matching
 *   colors as well. Supply a null pointer here if your graphs are not 
 *   edge-colored.
 * \param edge_color2 The edge color vector for the second graph.
 * \param map12 Pointer to a vector or \c NULL. If not \c NULL, then an
 *    isomorphic mapping from \p graph1 to \p graph2 is stored here.
 * \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
 *    an isomorphic mapping from \p graph2 to \p graph1 is stored
 *    here.
 * \param isohandler_fn A pointer to a function of type \ref
 *   igraph_isohandler_t. This will be called whenever a subgraph
 *   isomorphism is found. If the function returns with a non-zero value
 *   then the search is continued, otherwise it stops and the function
 *   returns. 
 * \param node_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two nodes are compatible.
 * \param edge_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two edges are compatible.
 * \param arg Extra argument to supply to functions \p isohandler_fn, \p
 *   node_compat_fn and \p edge_compat_fn.
 * \return Error code.
 * 
 * Time complexity: exponential.
 */

int igraph_subisomorphic_function_vf2(const igraph_t *graph1, 
				      const igraph_t *graph2,
				      const igraph_vector_int_t *vertex_color1,
				      const igraph_vector_int_t *vertex_color2,
				      const igraph_vector_int_t *edge_color1,
				      const igraph_vector_int_t *edge_color2,
				      igraph_vector_t *map12,
				      igraph_vector_t *map21,
				      igraph_isohandler_t *isohandler_fn,
				      igraph_isocompat_t *node_compat_fn,
				      igraph_isocompat_t *edge_compat_fn,
				      void *arg) {
  
  long int no_of_nodes1=igraph_vcount(graph1), 
    no_of_nodes2=igraph_vcount(graph2);
  long int no_of_edges1=igraph_ecount(graph1), 
    no_of_edges2=igraph_ecount(graph2);
  igraph_vector_t mycore_1, mycore_2, *core_1=&mycore_1, *core_2=&mycore_2;
  igraph_vector_t in_1, in_2, out_1, out_2;
  long int in_1_size=0, in_2_size=0, out_1_size=0, out_2_size=0;
  igraph_vector_t *inneis_1, *inneis_2, *outneis_1, *outneis_2;
  long int matched_nodes=0;
  long int depth;
  long int cand1, cand2;
  long int last1, last2;
  igraph_stack_t path;
  igraph_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
  igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;

  if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
    IGRAPH_ERROR("Cannot compare directed and undirected graphs",
		 IGRAPH_EINVAL);
  }

  if (no_of_nodes1 < no_of_nodes2 || 
      no_of_edges1 < no_of_edges2) {
    return 0;
  }

  if ( (vertex_color1 && !vertex_color2) || (!vertex_color1 && vertex_color2) ) {
    IGRAPH_WARNING("Only one graph is vertex colored, colors will be ignored");
    vertex_color1=vertex_color2=0;
  }

  if ( (edge_color1 && !edge_color2) || (!edge_color1 && edge_color2) ) {
    IGRAPH_WARNING("Only one graph is edge colored, colors will be ignored");
    edge_color1=edge_color2=0;
  }

  if (vertex_color1) {
    if (igraph_vector_int_size(vertex_color1) != no_of_nodes1 ||
	igraph_vector_int_size(vertex_color2) != no_of_nodes2) {
      IGRAPH_ERROR("Invalid vertex color vector length", IGRAPH_EINVAL);
    }
  }

  if (edge_color1) {
    if (igraph_vector_int_size(edge_color1) != no_of_edges1 ||
	igraph_vector_int_size(edge_color2) != no_of_edges2) {
      IGRAPH_ERROR("Invalid edge color vector length", IGRAPH_EINVAL);
    }
  }

  /* Check color distribution */
  if (vertex_color1) {
    /* TODO */
  }

  /* Check edge color distribution */
  if (edge_color1) {
    /* TODO */
  }

  if (map12) {
    core_1=map12;
    IGRAPH_CHECK(igraph_vector_resize(core_1, no_of_nodes1));
  } else {
    IGRAPH_VECTOR_INIT_FINALLY(core_1, no_of_nodes1);
  }
  igraph_vector_fill(core_1, -1);
  if (map21) {
    core_2=map21;
    IGRAPH_CHECK(igraph_vector_resize(core_2, no_of_nodes2));
  } else {
    IGRAPH_VECTOR_INIT_FINALLY(core_2, no_of_nodes2);
  }
  igraph_vector_fill(core_2, -1);
  IGRAPH_VECTOR_INIT_FINALLY(&in_1, no_of_nodes1);
  IGRAPH_VECTOR_INIT_FINALLY(&in_2, no_of_nodes2);
  IGRAPH_VECTOR_INIT_FINALLY(&out_1, no_of_nodes1);
  IGRAPH_VECTOR_INIT_FINALLY(&out_2, no_of_nodes2);
  IGRAPH_CHECK(igraph_stack_init(&path, 0));
  IGRAPH_FINALLY(igraph_stack_destroy, &path);
  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN, 
					  IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj1);
  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT, 
					  IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj1);
  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN, 
					  IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj2);
  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT, 
					  IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj2);
  IGRAPH_VECTOR_INIT_FINALLY(&indeg1, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&indeg2, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&outdeg1, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&outdeg2, 0);

  IGRAPH_CHECK(igraph_stack_reserve(&path, no_of_nodes2*2));
  IGRAPH_CHECK(igraph_degree(graph1, &indeg1, igraph_vss_all(), 
			     IGRAPH_IN, IGRAPH_LOOPS));
  IGRAPH_CHECK(igraph_degree(graph2, &indeg2, igraph_vss_all(), 
			     IGRAPH_IN, IGRAPH_LOOPS));
  IGRAPH_CHECK(igraph_degree(graph1, &outdeg1, igraph_vss_all(), 
			     IGRAPH_OUT, IGRAPH_LOOPS));
  IGRAPH_CHECK(igraph_degree(graph2, &outdeg2, igraph_vss_all(), 
			     IGRAPH_OUT, IGRAPH_LOOPS));

  depth=0; last1=-1; last2=-1;
  while (depth >= 0) {
    long int i;
    
    IGRAPH_ALLOW_INTERRUPTION();

    cand1=-1; cand2=-1;
    /* Search for the next pair to try */
    if ((in_1_size < in_2_size) ||
	(out_1_size < out_2_size)) {
      /* step back, nothing to do */
    } else if (out_1_size > 0 && out_2_size > 0) {
      /**************************************************************/
      /* cand2, search not always needed */
      if (last2 >= 0) {
	cand2=last2;
      } else {
	i=0;
	while (cand2<0 && i<no_of_nodes2) {
	  if (VECTOR(out_2)[i]>0 && VECTOR(*core_2)[i] < 0) {
	    cand2=i;
	  }
	  i++;
	}
      }
      /* search for cand1 now, it should be bigger than last1 */
      i=last1+1;
      while (cand1<0 && i<no_of_nodes1) {
	if (VECTOR(out_1)[i]>0 && VECTOR(*core_1)[i] < 0) {
	  cand1=i;
	}
	i++;
      }
    } else if (in_1_size > 0 && in_2_size > 0) {
      /**************************************************************/
      /* cand2, search not always needed */
      if (last2 >= 0) {
	cand2=last2;
      } else {
	i=0;
	while (cand2<0 && i<no_of_nodes2) {
	  if (VECTOR(in_2)[i]>0 && VECTOR(*core_2)[i] < 0) {
	    cand2=i;
	  }
	  i++;
	}
      }
      /* search for cand1 now, should be bigger than last1 */
      i=last1+1;
      while (cand1<0 && i<no_of_nodes1) {
	if (VECTOR(in_1)[i]>0 && VECTOR(*core_1)[i] < 0) {
	  cand1=i;
	}
	i++;
      }
    } else {
      /**************************************************************/
      /* cand2, search not always needed */
      if (last2 >= 0) {
	cand2=last2;
      } else {
	i=0;
	while (cand2<0 && i<no_of_nodes2) {
	  if (VECTOR(*core_2)[i] < 0) { 
	    cand2=i;
	  }
	  i++;
	}
      }
      /* search for cand1, should be bigger than last1 */
      i=last1+1;
      while (cand1<0 && i<no_of_nodes1) {
	if (VECTOR(*core_1)[i] < 0) {
	  cand1=i;
	}
	i++;
      }
    }
        
    /* Ok, we have cand1, cand2 as candidates. Or not? */
    if (cand1<0 || cand2<0) {
      /**************************************************************/
      /* dead end, step back, if possible. Otherwise we'll terminate */
      if (depth >= 1) {
	last2=(long int) igraph_stack_pop(&path);
	last1=(long int) igraph_stack_pop(&path);
	matched_nodes -= 1;
	VECTOR(*core_1)[last1]=-1;
	VECTOR(*core_2)[last2]=-1;

	if (VECTOR(in_1)[last1] != 0) {
	  in_1_size += 1;
	}
	if (VECTOR(out_1)[last1] != 0) {
	  out_1_size += 1;
	}
	if (VECTOR(in_2)[last2] != 0) {
	  in_2_size += 1;
	} 
	if (VECTOR(out_2)[last2] != 0) {
	  out_2_size += 1;
	}
	
	inneis_1=igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) last1);
	for (i=0; i<igraph_vector_size(inneis_1); i++) {
	  long int node=(long int) VECTOR(*inneis_1)[i];
	  if (VECTOR(in_1)[node] == depth) {
	    VECTOR(in_1)[node]=0;
	    in_1_size -= 1;
	  }
	}
	outneis_1=igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) last1);
	for (i=0; i<igraph_vector_size(outneis_1); i++) {
	  long int node=(long int) VECTOR(*outneis_1)[i];
	  if (VECTOR(out_1)[node] == depth) {
	    VECTOR(out_1)[node]=0;
	    out_1_size -= 1;
	  }
	}
	inneis_2=igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) last2);
	for (i=0; i<igraph_vector_size(inneis_2); i++) {
	  long int node=(long int) VECTOR(*inneis_2)[i];
	  if (VECTOR(in_2)[node] == depth) {
	    VECTOR(in_2)[node]=0;
	    in_2_size -= 1;
	  }
	}
	outneis_2=igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) last2);
	for (i=0; i<igraph_vector_size(outneis_2); i++) {
	  long int node=(long int) VECTOR(*outneis_2)[i];
	  if (VECTOR(out_2)[node] == depth) {
	    VECTOR(out_2)[node]=0;
	    out_2_size -= 1;
	  }
	}
	
      }	/* end of stepping back */
      
      depth -= 1;

    } else {
      /**************************************************************/
      /* step forward if worth, check if worth first */
      long int xin1=0, xin2=0, xout1=0, xout2=0;
      igraph_bool_t end=0;
      inneis_1=igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
      outneis_1=igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
      inneis_2=igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
      outneis_2=igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
      if (VECTOR(indeg1)[cand1] < VECTOR(indeg2)[cand2] ||
	  VECTOR(outdeg1)[cand1] < VECTOR(outdeg2)[cand2]) {
	end=1;
      }
      if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
	end=1;
      }
      if (node_compat_fn && !node_compat_fn(graph1, graph2, 
					    (igraph_integer_t) cand1,
					    (igraph_integer_t) cand2, arg)) {
	end=1;
      }

      for (i=0; !end && i<igraph_vector_size(inneis_1); i++) {
	long int node=(long int) VECTOR(*inneis_1)[i];
	if (VECTOR(*core_1)[node] < 0) {
	  if (VECTOR(in_1)[node] != 0) {
	    xin1++;
	  }
	  if (VECTOR(out_1)[node] != 0) {
	    xout1++;
	  }
	}
      }
      for (i=0; !end && i<igraph_vector_size(outneis_1); i++) {
	long int node=(long int) VECTOR(*outneis_1)[i];
	if (VECTOR(*core_1)[node] < 0) {
	  if (VECTOR(in_1)[node] != 0) {
	    xin1++;
	  }
	  if (VECTOR(out_1)[node] != 0) {
	    xout1++;
	  }
	}
      }      
      for (i=0; !end && i<igraph_vector_size(inneis_2); i++) {
	long int node=(long int) VECTOR(*inneis_2)[i];
	if (VECTOR(*core_2)[node] >= 0) {
	  long int node2=(long int) VECTOR(*core_2)[node];
	  /* check if there is a node2->cand1 edge */
	  if (!igraph_vector_binsearch2(inneis_1, node2)) {
	    end=1;
	  } else if (edge_color1 || edge_compat_fn) {
	    igraph_integer_t eid1, eid2;
	    igraph_get_eid(graph1, &eid1, (igraph_integer_t) node2, 
			   (igraph_integer_t) cand1, /*directed=*/ 1, 
			   /*error=*/ 1);
	    igraph_get_eid(graph2, &eid2, (igraph_integer_t) node, 
			   (igraph_integer_t) cand2, /*directed=*/ 1, 
			   /*error=*/ 1);
	    if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] != 
		VECTOR(*edge_color2)[(long int)eid2]) {
	      end=1;
	    }
	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, 
						  eid1, eid2, arg)) {
	      end=1;
	    }
	  }
	} else { 
	  if (VECTOR(in_2)[node] != 0) {
	    xin2++;
	  }
	  if (VECTOR(out_2)[node] != 0) {
	    xout2++;
	  }
	}
      }      
      for (i=0; !end && i<igraph_vector_size(outneis_2); i++) {
	long int node=(long int) VECTOR(*outneis_2)[i];
	if (VECTOR(*core_2)[node] >= 0) {
	  long int node2=(long int) VECTOR(*core_2)[node];
	  /* check if there is a cand1->node2 edge */
	  if (!igraph_vector_binsearch2(outneis_1, node2)) {
	    end=1;
	  } else if (edge_color1 || edge_compat_fn) {
	    igraph_integer_t eid1, eid2;
	    igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1, 
			   (igraph_integer_t) node2, /*directed=*/ 1, 
			   /*error=*/ 1);
	    igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2, 
			   (igraph_integer_t) node, /*directed=*/ 1,
			   /*error=*/ 1);
	    if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] != 
		VECTOR(*edge_color2)[(long int)eid2]) {
	      end=1;
	    }
	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, 
						  eid1, eid2, arg)) {
	      end=1;
	    }
	  }
	} else {
	  if (VECTOR(in_2)[node] != 0) {
	    xin2++;
	  }
	  if (VECTOR(out_2)[node] != 0) {
	    xout2++;
	  }
	}
      }      
      
      if (!end && (xin1>=xin2 && xout1>=xout2)) {
	/* Ok, we add the (cand1, cand2) pair to the mapping */
	depth += 1;
	IGRAPH_CHECK(igraph_stack_push(&path, cand1));
	IGRAPH_CHECK(igraph_stack_push(&path, cand2));
	matched_nodes += 1;
	VECTOR(*core_1)[cand1]=cand2;
	VECTOR(*core_2)[cand2]=cand1;
	
	/* update in_*, out_* */
	if (VECTOR(in_1)[cand1] != 0) {
	  in_1_size -= 1;
	}
	if (VECTOR(out_1)[cand1] != 0) {
	  out_1_size -= 1;
	}
	if (VECTOR(in_2)[cand2] != 0) {
	  in_2_size -= 1;
	}
	if (VECTOR(out_2)[cand2] != 0) {
	  out_2_size -= 1;
	}
	
	inneis_1=igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
	for (i=0; i<igraph_vector_size(inneis_1); i++) {
	  long int node=(long int) VECTOR(*inneis_1)[i];
	  if (VECTOR(in_1)[node]==0 && VECTOR(*core_1)[node] < 0) {
	    VECTOR(in_1)[node]=depth;
	    in_1_size += 1;
	  }
	}
	outneis_1=igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
	for (i=0; i<igraph_vector_size(outneis_1); i++) {
	  long int node=(long int) VECTOR(*outneis_1)[i];
	  if (VECTOR(out_1)[node]==0 && VECTOR(*core_1)[node] < 0) {
	    VECTOR(out_1)[node]=depth;
	    out_1_size += 1;
	  }
	}
	inneis_2=igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
	for (i=0; i<igraph_vector_size(inneis_2); i++) {
	  long int node=(long int) VECTOR(*inneis_2)[i];
	  if (VECTOR(in_2)[node]==0 && VECTOR(*core_2)[node] < 0) {
	    VECTOR(in_2)[node]=depth;
	    in_2_size += 1;
	  }
	}
	outneis_2=igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
	for (i=0; i<igraph_vector_size(outneis_2); i++) {
	  long int node=(long int) VECTOR(*outneis_2)[i];
	  if (VECTOR(out_2)[node]==0 && VECTOR(*core_2)[node] < 0) {
	    VECTOR(out_2)[node]=depth;
	    out_2_size += 1;
	  }
	}
	last1=-1; last2=-1;    	      /* this the first time here */
      } else {
	last1=cand1;
	last2=cand2;
      }
      
    }

    if (matched_nodes==no_of_nodes2 && isohandler_fn) { 
      if (!isohandler_fn(core_1, core_2, arg)) {
	break;
      }
    }
  }

  igraph_vector_destroy(&outdeg2);
  igraph_vector_destroy(&outdeg1);
  igraph_vector_destroy(&indeg2);
  igraph_vector_destroy(&indeg1);
  igraph_lazy_adjlist_destroy(&outadj2);
  igraph_lazy_adjlist_destroy(&inadj2);
  igraph_lazy_adjlist_destroy(&outadj1);
  igraph_lazy_adjlist_destroy(&inadj1);  
  igraph_stack_destroy(&path);
  igraph_vector_destroy(&out_2);
  igraph_vector_destroy(&out_1);
  igraph_vector_destroy(&in_2);
  igraph_vector_destroy(&in_1);
  IGRAPH_FINALLY_CLEAN(13);
  if (!map21) { 
    igraph_vector_destroy(core_2);
    IGRAPH_FINALLY_CLEAN(1);
  }    
  if (!map12) {
    igraph_vector_destroy(core_1);
    IGRAPH_FINALLY_CLEAN(1);
  }

  return 0;
}

igraph_bool_t igraph_i_subisomorphic_vf2(const igraph_vector_t *map12,
					 const igraph_vector_t *map21,
					 void *arg) {
  igraph_i_iso_cb_data_t *data = arg;
  igraph_bool_t *iso = data->arg;
  IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
  *iso=1;
  return 0; /* stop */
}

/**
 * \function igraph_subisomorphic_vf2
 * Decide subgraph isomorphism using VF2
 * 
 * Decides whether a subgraph of \p graph1 is isomorphic to \p
 * graph2. It uses \ref igraph_subisomorphic_function_vf2().
 * \param graph1 The first input graph, may be directed or
 *    undirected. This is supposed to be the larger graph.
 * \param graph2 The second input graph, it must have the same
 *    directedness as \p graph1. This is supposed to be the smaller
 *    graph.
 * \param vertex_color1 An optional color vector for the first graph. If
 *   color vectors are given for both graphs, then the subgraph isomorphism is
 *   calculated on the colored graphs; i.e. two vertices can match
 *   only if their color also matches. Supply a null pointer here if
 *   your graphs are not colored.
 * \param vertex_color2 An optional color vector for the second graph. See
 *   the previous argument for explanation.
 * \param edge_color1 An optional edge color vector for the first
 *   graph. The matching edges in the two graphs must have matching
 *   colors as well. Supply a null pointer here if your graphs are not 
 *   edge-colored.
 * \param edge_color2 The edge color vector for the second graph.
 * \param iso Pointer to a boolean. The result of the decision problem
 *    is stored here.
 * \param map12 Pointer to a vector or \c NULL. If not \c NULL, then an
 *    isomorphic mapping from \p graph1 to \p graph2 is stored here.
 * \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
 *    an isomorphic mapping from \p graph2 to \p graph1 is stored
 *    here.
 * \param node_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two nodes are compatible.
 * \param edge_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two edges are compatible.
 * \param arg Extra argument to supply to functions \p node_compat_fn 
 *   and \p edge_compat_fn. 
 * \return Error code.
 * 
 * Time complexity: exponential.
 */

int igraph_subisomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2, 
			     const igraph_vector_int_t *vertex_color1,
			     const igraph_vector_int_t *vertex_color2,
			     const igraph_vector_int_t *edge_color1,
			     const igraph_vector_int_t *edge_color2,
			     igraph_bool_t *iso, igraph_vector_t *map12, 
			     igraph_vector_t *map21,
			     igraph_isocompat_t *node_compat_fn,
			     igraph_isocompat_t *edge_compat_fn,
			     void *arg) {

  igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, iso, arg };
  igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
  igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;

  *iso=0;
  IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2, 
						 vertex_color1, vertex_color2,
						 edge_color1, edge_color2,
						 map12, map21,
						 (igraph_isohandler_t *)
						 igraph_i_subisomorphic_vf2,
						 ncb, ecb, &data));
  if (! *iso) {
    if (map12) { igraph_vector_clear(map12); }
    if (map21) { igraph_vector_clear(map21); }
    }
  return 0;
}

igraph_bool_t igraph_i_count_subisomorphisms_vf2(const igraph_vector_t *map12,
						 const igraph_vector_t *map21,
						 void *arg) {
  igraph_i_iso_cb_data_t *data = arg;
  igraph_integer_t *count = data->arg;
  IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
  *count += 1;
  return 1;			/* always continue */
}
  
/**
 * \function igraph_count_subisomorphisms_vf2
 * Number of subgraph isomorphisms using VF2
 * 
 * Count the number of isomorphisms between subgraphs of \p graph1 and
 * \p graph2. This function uses \ref
 * igraph_subisomorphic_function_vf2().
 * \param graph1 The first input graph, may be directed or
 *    undirected. This is supposed to be the larger graph.
 * \param graph2 The second input graph, it must have the same
 *    directedness as \p graph1. This is supposed to be the smaller
 *    graph.
 * \param vertex_color1 An optional color vector for the first graph. If
 *   color vectors are given for both graphs, then the subgraph isomorphism is
 *   calculated on the colored graphs; i.e. two vertices can match
 *   only if their color also matches. Supply a null pointer here if
 *   your graphs are not colored.
 * \param vertex_color2 An optional color vector for the second graph. See
 *   the previous argument for explanation.
 * \param edge_color1 An optional edge color vector for the first
 *   graph. The matching edges in the two graphs must have matching
 *   colors as well. Supply a null pointer here if your graphs are not 
 *   edge-colored.
 * \param edge_color2 The edge color vector for the second graph.
 * \param count Pointer to an integer. The number of subgraph
 *    isomorphisms is stored here.
 * \param node_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two nodes are compatible.
 * \param edge_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two edges are compatible.
 * \param arg Extra argument to supply to functions \p node_compat_fn and
 *   \p edge_compat_fn. 
 * \return Error code.
 * 
 * Time complexity: exponential.
 */

int igraph_count_subisomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2, 
				     const igraph_vector_int_t *vertex_color1,
				     const igraph_vector_int_t *vertex_color2,
				     const igraph_vector_int_t *edge_color1,
				     const igraph_vector_int_t *edge_color2,
				     igraph_integer_t *count,
				     igraph_isocompat_t *node_compat_fn,
				     igraph_isocompat_t *edge_compat_fn,
				     void *arg) {

  igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, 
				  count, arg };
  igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
  igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
  *count=0;
  IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2, 
					 vertex_color1, vertex_color2, 
					 edge_color1, edge_color2,
					 0, 0,
					 (igraph_isohandler_t*)
					 igraph_i_count_subisomorphisms_vf2,
					 ncb, ecb, &data));
    return 0;
  }
  
void igraph_i_get_subisomorphisms_free(igraph_vector_ptr_t *data) {
  long int i, n=igraph_vector_ptr_size(data);
  for (i=0; i<n; i++) {
    igraph_vector_t *vec=VECTOR(*data)[i];
    igraph_vector_destroy(vec);
    igraph_free(vec);
  }
}

igraph_bool_t igraph_i_get_subisomorphisms_vf2(const igraph_vector_t *map12,
					       const igraph_vector_t *map21,
					       void *arg) {

  igraph_i_iso_cb_data_t *data = arg;
  igraph_vector_ptr_t *vector = data->arg;
  igraph_vector_t *newvector=igraph_Calloc(1, igraph_vector_t);
  IGRAPH_UNUSED(map12);
  if (!newvector) { 
    igraph_error("Out of memory", __FILE__, __LINE__, IGRAPH_ENOMEM);
    return 0;			/* stop right here */
  }
  IGRAPH_FINALLY(igraph_free, newvector);
  IGRAPH_CHECK(igraph_vector_copy(newvector, map21));
  IGRAPH_FINALLY(igraph_vector_destroy, newvector);
  IGRAPH_CHECK(igraph_vector_ptr_push_back(vector, newvector));
  IGRAPH_FINALLY_CLEAN(2);
  
  return 1;			/* continue finding subisomorphisms */
}

/** 
 * \function igraph_get_subisomorphisms_vf2
 * Return all subgraph isomorphic mappings
 * 
 * This function collects all isomorphic mappings of \p graph2 to a
 * subgraph of \p graph1. It uses the \ref
 * igraph_subisomorphic_function_vf2() function.
 * \param graph1 The first input graph, may be directed or
 *    undirected. This is supposed to be the larger graph.
 * \param graph2 The second input graph, it must have the same
 *    directedness as \p graph1. This is supposed to be the smaller
 *    graph.
 * \param vertex_color1 An optional color vector for the first graph. If
 *   color vectors are given for both graphs, then the subgraph isomorphism is
 *   calculated on the colored graphs; i.e. two vertices can match
 *   only if their color also matches. Supply a null pointer here if
 *   your graphs are not colored.
 * \param vertex_color2 An optional color vector for the second graph. See
 *   the previous argument for explanation.
 * \param edge_color1 An optional edge color vector for the first
 *   graph. The matching edges in the two graphs must have matching
 *   colors as well. Supply a null pointer here if your graphs are not 
 *   edge-colored.
 * \param edge_color2 The edge color vector for the second graph.
 * \param maps Pointer vector. On return it contains pointers to
 *   <type>igraph_vector_t</type> objects, each vector is an
 *   isomorphic mapping of \p graph2 to a subgraph of \p graph1. Please note that
 *   you need to 1) Destroy the vectors via \ref
 *   igraph_vector_destroy(), 2) free them via
 *   <function>free()</function> and then 3) call \ref
 *   igraph_vector_ptr_destroy() on the pointer vector to deallocate all
 *   memory when \p maps is no longer needed.
 * \param node_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two nodes are compatible.
 * \param edge_compat_fn A pointer to a function of type \ref 
 *   igraph_isocompat_t. This function will be called by the algorithm to
 *   determine whether two edges are compatible.
 * \param arg Extra argument to supply to functions \p node_compat_fn 
 *   and \p edge_compat_fn.
 * \return Error code.
 * 
 * Time complexity: exponential.
 */
 
int igraph_get_subisomorphisms_vf2(const igraph_t *graph1,
				   const igraph_t *graph2,
				   const igraph_vector_int_t *vertex_color1,
				   const igraph_vector_int_t *vertex_color2,
				   const igraph_vector_int_t *edge_color1,
				   const igraph_vector_int_t *edge_color2,
				   igraph_vector_ptr_t *maps,
				   igraph_isocompat_t *node_compat_fn,
				   igraph_isocompat_t *edge_compat_fn,
				   void *arg) {
  
  igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, maps, arg };
  igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
  igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;

  igraph_vector_ptr_clear(maps);
  IGRAPH_FINALLY(igraph_i_get_subisomorphisms_free, maps);
  IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2, 
					 vertex_color1, vertex_color2,
					 edge_color1, edge_color2,
					 0, 0,
					 (igraph_isohandler_t*)
					 igraph_i_get_subisomorphisms_vf2,
					 ncb, ecb, &data));
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/**
 * \function igraph_permute_vertices
 * Permute the vertices
 * 
 * This function creates a new graph from the input graph by permuting
 * its vertices according to the specified mapping. Call this function
 * with the output of \ref igraph_canonical_permutation() to create
 * the canonical form of a graph.
 * \param graph The input graph.
 * \param res Pointer to an uninitialized graph object. The new graph
 *    is created here.
 * \param permutation The permutation to apply. Vertex 0 is mapped to
 *    the first element of the vector, vertex 1 to the second,
 * etc. Note that it is not checked that the vector contains every
 *    element only once, and no range checking is performed either.
 * \return Error code.
 * 
 * Time complexity: O(|V|+|E|), linear in terms of the number of
 * vertices and edges.
 */

int igraph_permute_vertices(const igraph_t *graph, igraph_t *res,
			    const igraph_vector_t *permutation) {

  long int no_of_nodes=igraph_vcount(graph);
  long int no_of_edges=igraph_ecount(graph);
  igraph_vector_t edges;
  long int i, p=0;
  
  if (igraph_vector_size(permutation) != no_of_nodes) {
    IGRAPH_ERROR("Permute vertices: invalid permutation vector size", IGRAPH_EINVAL);
  }
  
  IGRAPH_VECTOR_INIT_FINALLY(&edges, no_of_edges*2);

  for (i=0; i<no_of_edges; i++) {
    VECTOR(edges)[p++] = VECTOR(*permutation)[ (long int) IGRAPH_FROM(graph, i) ];
    VECTOR(edges)[p++] = VECTOR(*permutation)[ (long int) IGRAPH_TO(graph, i) ];
  }
  
  IGRAPH_CHECK(igraph_create(res, &edges, (igraph_integer_t) no_of_nodes, 
			     igraph_is_directed(graph)));
  
  /* Attributes */
  if (graph->attr) {
    igraph_vector_t index;
    igraph_vector_t vtypes;
    IGRAPH_I_ATTRIBUTE_DESTROY(res);
    IGRAPH_I_ATTRIBUTE_COPY(res, graph, /*graph=*/1, /*vertex=*/0, /*edge=*/1);
    IGRAPH_VECTOR_INIT_FINALLY(&vtypes, 0);
    IGRAPH_CHECK(igraph_i_attribute_get_info(graph, 0, 0, 0, &vtypes, 0, 0));
    if (igraph_vector_size(&vtypes) != 0) {      
      IGRAPH_VECTOR_INIT_FINALLY(&index, no_of_nodes);
      for (i=0; i<no_of_nodes; i++) {
	VECTOR(index)[ (long int) VECTOR(*permutation)[i] ] = i;
      }
      IGRAPH_CHECK(igraph_i_attribute_permute_vertices(graph, res, &index));
      igraph_vector_destroy(&index);
      IGRAPH_FINALLY_CLEAN(1);
    }
    igraph_vector_destroy(&vtypes);
    IGRAPH_FINALLY_CLEAN(1);
  }
  
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/** 
 * \section about_bliss 
 * 
 * <para>
 * BLISS is a successor of the famous NAUTY algorithm and
 * implementation. While using the same ideas in general, with better
 * heuristics and data structure BLISS outperforms NAUTY on most
 * graphs.
 * </para>
 * 
 * <para>
 * BLISS was developed and implemented by Tommi Junttila and Petteri Kaski at 
 * Helsinki University of Technology, Finland. See Tommi Juntilla's 
 * homepage at http://www.tcs.hut.fi/~tjunttil/ and the publication at 
 * http://www.siam.org/proceedings/alenex/2007/alx07_013junttilat.pdf
 * for more information.
 * </para>
 * 
 * <para>
 * BLISS version 0.73 is included in igraph.
 * </para>
 */

/**
 * \function igraph_isomorphic_bliss
 * Graph isomorphism via BLISS
 * 
 * This function uses the BLISS graph isomorphism algorithm, a
 * successor of the famous NAUTY algorithm and implementation. BLISS
 * is open source and licensed according to the GNU GPL. See 
 * http://www.tcs.hut.fi/Software/bliss/index.html for
 * details. Currently the 0.73 version of BLISS is included in igraph.
 *
 * </para><para>
 *
 * \param graph1 The first input graph. Multiple edges between the same nodes
 *   are not supported and will cause an incorrect result to be returned.
 * \param graph2 The second input graph. Multiple edges between the same nodes
 *   are not supported and will cause an incorrect result to be returned.
 * \param colors1 An optional vertex color vector for the first graph. Supply a
 *   null pointer if your graph is not colored.
 * \param colors2 An optional vertex color vector for the second graph. Supply a
 *   null pointer if your graph is not colored.
 * \param iso Pointer to a boolean, the result is stored here.
 * \param map12 A vector or \c NULL pointer. If not \c NULL then an
 *   isomorphic mapping from \p graph1 to \p graph2 is stored here.
 *   If the input graphs are not isomorphic then this vector is
 *   cleared, i.e. it will have length zero.
 * \param map21 Similar to \p map12, but for the mapping from \p
 *   graph2 to \p graph1. 
 * \param sh Splitting heuristics to be used for the graphs. See
 *   \ref igraph_bliss_sh_t.
 * \param info1 If not \c NULL, information about the canonization of
 *    the first input graph is stored here. See \ref igraph_bliss_info_t
 *    for details. Note that if the two graphs have different number
 *    of vertices or edges, then this is not filled.
 * \param info2 Same as \p info1, but for the second graph.
 * \return Error code.
 * 
 * Time complexity: exponential, but in practice it is quite fast.
 */

int igraph_isomorphic_bliss(const igraph_t *graph1, const igraph_t *graph2,
                const igraph_vector_int_t *colors1, const igraph_vector_int_t *colors2,
			    igraph_bool_t *iso, igraph_vector_t *map12, 
			    igraph_vector_t *map21,
                igraph_bliss_sh_t sh,
			    igraph_bliss_info_t *info1, igraph_bliss_info_t *info2) {
  
  long int no_of_nodes=igraph_vcount(graph1);
  long int no_of_edges=igraph_ecount(graph1);
  igraph_vector_t perm1, perm2;
  igraph_vector_t vmap12, *mymap12=&vmap12;  
  igraph_vector_t from, to, index;
  igraph_vector_t from2, to2, index2;
  igraph_bool_t directed;
  long int i, j;

  *iso=0;
  if (info1) {
    info1->nof_nodes = info1->nof_leaf_nodes = info1->nof_bad_nodes =
        info1->nof_canupdates = info1->max_level = info1->nof_generators = -1;
    info1->group_size = 0;
  }
  if (info2) {
    info2->nof_nodes = info2->nof_leaf_nodes = info2->nof_bad_nodes =
        info2->nof_canupdates = info2->max_level = info2->nof_generators = -1;
    info2->group_size = 0;
  }

  directed = igraph_is_directed(graph1);
  if (igraph_is_directed(graph2) != directed) {
    IGRAPH_ERROR("Cannot compare directed and undirected graphs",
		 IGRAPH_EINVAL);
  }
  if ((colors1 == NULL || colors2 == NULL) && colors1 != colors2) {
    IGRAPH_WARNING("Only one of the graphs is vertex colored, colors will be ignored");
    colors1 = NULL; colors2 = NULL;
  }

  if (no_of_nodes != igraph_vcount(graph2) ||
      no_of_edges != igraph_ecount(graph2)) {
    if (map12) { igraph_vector_clear(map12); }
    if (map21) { igraph_vector_clear(map21); }
    return 0;
  }

  if (map12) {
    mymap12=map12;
  } else {
    IGRAPH_VECTOR_INIT_FINALLY(mymap12, 0);
  }

  IGRAPH_VECTOR_INIT_FINALLY(&perm1, no_of_nodes);
  IGRAPH_VECTOR_INIT_FINALLY(&perm2, no_of_nodes);
  
  IGRAPH_CHECK(igraph_canonical_permutation(graph1, colors1, &perm1, sh, info1));
  IGRAPH_CHECK(igraph_canonical_permutation(graph2, colors2, &perm2, sh, info2));

  IGRAPH_CHECK(igraph_vector_resize(mymap12, no_of_nodes));
    
  /* The inverse of perm2 is produced in mymap12 */
  for (i=0; i<no_of_nodes; i++) {
    VECTOR(*mymap12)[ (long int)VECTOR(perm2)[i] ] = i;
  }
  /* Now we produce perm2^{-1} o perm1 in perm2 */
  for (i=0; i<no_of_nodes; i++) {
    VECTOR(perm2)[i] = VECTOR(*mymap12)[ (long int) VECTOR(perm1)[i] ];
  }
  /* Copy it to mymap12 */
  igraph_vector_update(mymap12, &perm2);
  
  igraph_vector_destroy(&perm1);
  igraph_vector_destroy(&perm2);
  IGRAPH_FINALLY_CLEAN(2);

  /* Check isomorphism, we apply the permutation in mymap12 to graph1
     and should get graph2 */
  
  IGRAPH_VECTOR_INIT_FINALLY(&from, no_of_edges);
  IGRAPH_VECTOR_INIT_FINALLY(&to, no_of_edges);
  IGRAPH_VECTOR_INIT_FINALLY(&index, no_of_edges);
  IGRAPH_VECTOR_INIT_FINALLY(&from2, no_of_edges*2);
  IGRAPH_VECTOR_INIT_FINALLY(&to2, no_of_edges);
  IGRAPH_VECTOR_INIT_FINALLY(&index2, no_of_edges);  
  
  for (i=0; i<no_of_edges; i++) {
    VECTOR(from)[i] = VECTOR(*mymap12)[ (long int) IGRAPH_FROM(graph1, i) ];
    VECTOR(to)[i]   = VECTOR(*mymap12)[ (long int) IGRAPH_TO  (graph1, i) ];
    if (! directed && VECTOR(from)[i] < VECTOR(to)[i]) {
      igraph_real_t tmp=VECTOR(from)[i];
      VECTOR(from)[i] = VECTOR(to)[i];
      VECTOR(to)[i] = tmp;
    }
  }
  igraph_vector_order(&from, &to, &index, no_of_nodes);
  
  igraph_get_edgelist(graph2, &from2, /*bycol=*/ 1);
  for (i=0, j=no_of_edges; i<no_of_edges; i++, j++) {
    VECTOR(to2)[i] = VECTOR(from2)[j];
    if (! directed && VECTOR(from2)[i] < VECTOR(to2)[i]) {
      igraph_real_t tmp=VECTOR(from2)[i];
      VECTOR(from2)[i] = VECTOR(to2)[i];
      VECTOR(to2)[i] = tmp;
    }
  }
  igraph_vector_resize(&from2, no_of_edges);
  igraph_vector_order(&from2, &to2, &index2, no_of_nodes);
  
  *iso=1;
  for (i=0; i<no_of_edges; i++) {
    long int i1=(long int) VECTOR(index)[i];
    long int i2=(long int) VECTOR(index2)[i];
    if (VECTOR(from)[i1] != VECTOR(from2)[i2] ||
	VECTOR(to)[i1] != VECTOR(to2)[i2]) {
      *iso=0;
      break;
    }
  }

  /* If the graphs are coloured, we also need to check that applying the
     permutation mymap12 to colors1 gives colors2. */
  if (*iso && colors1 != NULL) {
    for (i=0; i < no_of_nodes; i++) {
      if (VECTOR(*colors1)[ (long int) VECTOR(*mymap12)[i] ] != VECTOR(*colors2)[i]) {
          *iso = 0;
          break;
      }
    }
  }
  
  igraph_vector_destroy(&index2);
  igraph_vector_destroy(&to2);
  igraph_vector_destroy(&from2);
  igraph_vector_destroy(&index);
  igraph_vector_destroy(&to);
  igraph_vector_destroy(&from);
  IGRAPH_FINALLY_CLEAN(6);
  
  if (*iso) {
    /* The inverse of mymap12 */
    if (map21) {
      IGRAPH_CHECK(igraph_vector_resize(map21, no_of_nodes));
      for (i=0; i<no_of_nodes; i++) {
        VECTOR(*map21)[ (long int) VECTOR(*mymap12)[i] ] = i;
      }
    }
  } else {
    if (map12) { igraph_vector_clear(map12); }
    if (map21) { igraph_vector_clear(map21); }
  }
  
  if (!map12) {
    igraph_vector_destroy(mymap12);
    IGRAPH_FINALLY_CLEAN(1);
  }
  
  return 0;
}
